在求解除法取模问题 $(a/b)\%m$ 时，我们可以转化为 $(a\%(b×m))/b$ ，
但是如果 $b$ 很大，则会出现爆精度问题，所以我们避免使用除法直接计算。
可以使用逆元将除法转换为乘法：假设 $b$ 存在乘法逆元，即与 $m$ 互质（充要条件）。
设 $c$ 是 $b$ 的逆元，即 $b×c≡1(mod~m)$
那么有 $a/b=(a/b)×1=(a/b)×b×c=a×c(mod~m)$
即，除以一个数取模等于乘以这个数的逆元取模
- 逆元求解一般利用扩欧。
-
当 $m$ 为质数的时候直接使用费马小定理， $m$ 非质数使用欧拉函数。
- 当 $m$ 为质数的时候，神奇的线性方法。
扩展欧几里得算法
要求 $a,m$ 互素，存在唯一解。
int extgcd(int a, int b, int& x, int& y)
{
int d = a;
if(b != 0)
{
d = extgcd(b, a % b, y, x);
y -= (a / b) * x;
}
else
{
x = 1;
y = 0;
}
return d;
}
int mod_inverse(int a, int m)
{
int x, y;
extgcd(a, m, x, y);
return (m + x % m) % m;
}
费马小定理
在 $p$ 是素数的情况下，对任意整数 $x$ 都有 $x^p≡x(mod~p)$ 。
如果 $x$ 无法被 $p$ 整除，则有 $x^{p−1}≡1(mod~p)$ 。
可以在 $p$ 为素数的情况下求出一个数的逆元， $x×x^{p−2}≡1(mod~p)$ ， $x^{p−2}$ 即为 $x$ 的逆元。
ll mult(ll a,ll n) //求a^n%mod
{
ll s=1;
while(n)
{
if(n&1)s=s*a%mod;
a=a*a%mod;
n>>=1;
}
return s;
} //mult(a,n-2);
欧拉函数
令 $ϕ(m)$ 表示小于等于 $m$ 且与 $m$ 互素的正整数的个数。
如果 $x$ 和 $m$ 互质，则有 $x^{ϕ(m)}≡1(mod~m)$，即 $x×x^{ϕ(m)−1}≡1(mod~m)$ ，$x^{ϕ(m)−1}$ 为 $x$ 的逆元。
在 $m$ 为质数的情况下， $ϕ(m)=m−1$ ，即为费马小定理。
思路：
求出欧拉函数的值，利用欧拉函数的积性性质：
对于任意整数 $n$ ，可以将它分解 $n=p_1^{k1}×p_2^{k2}×p_3^{k3}…p_m^{km}$ ，其中 $p_i$ 为质数， $ϕ(n)=ϕ(p_1^{k1})×ϕ(p_2^{k2})…ϕ(p_m^{km})$ 。
最后转化为 $ϕ(n)=n×\prod(p_i−1)/p_i$
对给定 $n$ 进行整数分解，时间复杂度 $O(n)$ 。
int eurler_phi(int n)
{
int res = n;
for(int i = 2; i * i <= n; i++)
{
if(n % i == 0)
{
res = res / i * (i - 1);
while(n % i == 0) n /= i;
}
}
if(n != 1) res = res / n * (n - 1);
return res;
}
埃氏筛法求欧拉函数值的表，每次发现质因子就把他的倍数的欧拉函数乘上 $(p−1)×p$ 。
当 $n$ 为奇数时，有 $ϕ(2n)=ϕ(n)$
因为 $2n$ 是偶数，偶数与偶数一定不互素，所以只考虑 $2n$ 与小于它的奇数互素的情况，则恰好就等于 $n$ 的欧拉函数值。
int euler[maxn];
void euler_phi2()
{
for(int i = 0; i < maxn; i++) euler[i] = i;
for(int i = 2; i < maxn; ++i)
{
if(euler[i] == i)
{
for(int j = i; j < maxn; j += i)
{
euler[j] = euler[j] / i * (i - 1);
}
}
}
}
线性时间求所有逆元
规定 $p$ 为质数，且 $1^{−1}≡1(mod~p)$
设 $p=k×a+b,(bint inv[maxn];
inv[1] = 1;
for(int i = 2; i < maxn; i++)
inv[i] = (p - p / i) % p * inv[p % i];
Pingback: 乘法逆元数论篇【易懂教学】 – Dreame的博客
来了就要留下点什么，想了想给你好多赞吧
hahah，谢谢~(/ω＼*)……… (/ω•＼*)
我会很多数学方面的例如老师教的加法
我也会
以前上学时我数学也是很好的
以前我也是
…………………..这是数学么。。我数学最最最不好了
数论里面的