# Nickel_Angel's nest

The key to magic is inside of us.

### [数学]乘法逆元

posted on 2019-07-19 11:12:01 | under 学习笔记 |

---百度百科

# 2.求逆元的方法

## 1.拓展欧几里得求逆元

$$ax\,mod\,p = 1\,mod\,p$$

$$(ax - 1)\,mod\,p = 0$$

$$ax - 1 = kp$$

$$ax - kp = 1$$

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

long long a, b;

int exgcd(long long a, long long b, long long &x, long long &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}

int main()
{
scanf("%lld%lld", &a, &b);
long long x = 0, y = 0;
exgcd(a, b, x, y);
printf("%lld", (x % b + b) % b);//这里防止出现负数
return 0;
}

## 2.欧拉定理求逆元

$$ax \equiv a^{\varphi(p)} \pmod{p}$$

$$x \equiv a^{\varphi(p) - 1} \pmod{p}$$

$\varphi(n) = n \times (1 - \frac {1} {p_1}) \times (1 - \frac {1} {p_2}) \times \cdots \times (1 - \frac {1} {p_m}) = n \times \prod_{i = 1}^{m} (1 - \frac {1} {p_i})$

\begin{aligned} \varphi(n) & = \prod_{i = 1}^{m} \varphi(p_i^{k_i}) \\ & = \prod_{i = 1}^{m} p_i^{k_i} \times \prod_{i = 1}^{m} (1 - \frac {1} {p_i}) \\ & = n \times \prod_{i = 1}^{m} (1 - \frac {1} {p_i}) \end{aligned}

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

long long n, p;

long long phi(long long x)//求x的欧拉函数
{
long long res = x, tmp = x;//初始化答案为x
for (int i = 2; i * i <= tmp; ++i)
{
if (x % i == 0)
{
res = (res / i) % p * ((i - 1) % p) % p;//找到x的一个质因子,计算其对答案的贡献
while (x % i == 0) x /= i;//统计完答案后,除去该质因子
}
}
if (x > 1) res = (res / x) % p * ((x - 1) % p) % p;//防止漏筛质因子
return res;
}

long long power(long long a, long long b)//快速幂
{
long long res = 1;
while (b)
{
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}

int main()
{
scanf("%lld%lld", &n, &p);
long long tmp = phi(p) - 1;
printf("%lld", power(n, tmp));
return 0;
}

## 3.费马小定理求逆元

$$a^{p - 2} \equiv a^{-1} \pmod{p}$$

$1.$ 当 $b \equiv 0 \pmod{p}$ 时，费马小定理不成立，故无解。

$2.$ 本题 $a,b$ 数据范围很大，$long\,long$ 也存不下，故需要写快读，边读边取模。

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iostream>

using namespace std;

const int p = 19260817;

template<typename T>
inline void input(T &x)
{
x = 0;
char ch = getchar();
bool f = false;
while (!isdigit(ch))
{
f |= (ch == '-');
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch ^ 48);
x %= p;//边读边取模
ch = getchar();
}
x = f ? -x : x;
}

inline int power(int a, int b)//快速幂
{
int res = 1;
while (b)
{
if (b & 1) res = 1ll * res * a % p;
a = 1ll * a * a % p;
b >>= 1;
}
return res;
}

int main()
{
int a, b;
input(a), input(b);
if (!b)
puts("Angry!");//b % p = 0 时无解
else
printf("%d", (int)(1ll * a * power(b, p - 2) % p));
return 0;
}

## 4.线性求逆

$$ki + r \equiv 0 \pmod{p}$$

$$i^{-1}r^{-1}(ki + r) \equiv 0 \pmod{p}$$

$$kr^{-1} + i^{-1} \equiv 0 \pmod{p}$$

$$i^{-1} \equiv -kr^{-1} \pmod{p}$$

$$i^{-1} \equiv - \lfloor \frac {p} {i} \rfloor \times (p\,mod\,i)^{-1} \pmod{p}$$

$$i^{-1} \equiv (p - \lfloor \frac {p} {i} \rfloor) \times (p\,mod\,i)^{-1} \pmod{p}$$

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 3e6 + 10;
long long inv[maxn], n, p;

int main()
{
scanf("%lld%lld", &n, &p);
inv[0] = 0, inv[1] = 1;//初始化1的逆元为1
printf("%lld\n", inv[1]);
for (int i = 2; i <= n; ++i)
{
inv[i] = (p - p / i) * inv[p % i] % p;//上文中的式子
printf("%lld\n", inv[i]);
}
return 0;
}

## 5.离线逆元

$O(max(a_i))$ 的递推显然不适用，时间空间双双爆炸。

$$a^{-1} \times b^{-1} \equiv (ab)^{-1} \pmod{p}$$

$$a \times a^{-1} \equiv 1 \pmod{p} \quad b \times b^{-1} \equiv 1 \pmod{p}$$

$$a \times b \times a^{-1} \times b^{-1} \equiv 1 \pmod{p}$$

$$pre_i^{-1} = a_{i+1} \times pre_{i + 1}^{-1}(1 \leq i < n)$$

$$a_j^{-1} = pre_{j - 1} \times pre_j^{-1}(1 \leq j \leq n)$$

（其中 $pre_n^{-1}$ 已求出，$pre_0 = 1$）

#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>

using namespace std;

template<typename T>
inline void input(T &x)//本题卡常数,需要用快读
{
x = 0;
register char ch = getchar();
register bool f = false;
while (!isdigit(ch))
{
f |= (ch == '-');
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x = f ? -x : x;
}

const int maxn = 5e6 + 10;
int n, p, k, a[maxn], inv[maxn], pre[maxn], inv_pre[maxn];

inline int power(int a, int b, int p)
{
int res = 1;
while (b)
{
if (b & 1) res = 1ll * res * a % p;
a = 1ll * a * a % p;
b >>= 1;
}
return res;
}

int main()
{
input(n), input(p), input(k);
pre[0] = 1;//初始化
for (register int i = 1; i <= n; ++i)
{
input(a[i]);
pre[i] = 1ll * pre[i - 1] * a[i] % p;//计算前缀积
}
inv_pre[n] = power(pre[n], p - 2, p);//求出前缀积的逆元
for (register int i = n; i > 0; --i)//递推求逆元
{
inv[i] = 1ll * pre[i - 1] * inv_pre[i] % p;
inv_pre[i - 1] = 1ll * inv_pre[i] * a[i] % p;
}
int ans = 0;//计算题目中式子的值
for (register int i = 1, t = k; i <= n; ++i)
{
ans = (1ll * inv[i] * t % p + ans) % p;
t = 1ll * t * k % p;
}
printf("%d", ans);
return 0;
}

# 3.后记

$Upd\,2019-8-21:$

$Upd\,2019-8-23:$

$Upd\,2019-8-24:$