乘法逆元小结

在求解除法取模问题(a/b)%m时，我们可以转化为(a%(b∗m))/b， 但是如果b很大，则会出现爆精度问题，所以我们避免使用除法直接计算。 可以使用逆元将除法转换为乘法： 假设b存在乘法逆元，即与m互质（充要条件）。设c是b的逆元，即b∗c≡1(modm)，那么有a/b=(a/b)∗1=(a/b)∗b∗c=a∗c(modm) 即，除以一个数取模等于乘以这个数的逆元取模。

1.逆元求解一般利用扩欧。 2.当m为质数的时候直接使用费马小定理，m非质数使用欧拉函数。 3.当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; }

费马小定理：

代码：

利用快速幂求出逆元

欧拉函数：

代码：

关键是求出欧拉函数的值。 利用欧拉函数的积性性质：

对给定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); } } } }

线性时间求所有逆元：

代码：

` int inv[maxn]; inv[1] = 1; for(int i = 2; i < maxn; i++) inv[i] = (p - p / i) * inv[p % i] % p;

`