『数论』乘法逆元

『数论』乘法逆元

在求解除法取模问题 (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

费马小定理

在 p 是素数的情况下，对任意整数 x 都有 xp≡x(mod p)

如果 x 无法被 p 整除，则有 xp−1≡1(mod p)

可以在 p 为素数的情况下求出一个数的逆元， x×xp−2≡1(mod p) ， xp−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=pk11×pk22×pk33...pkmm ，其中 pi 为质数， ϕ(n)=ϕ(pk11)×ϕ(pk22)...ϕ(pkmm)最后转化为 ϕ(n)=n×∏(pi−1)/pi对给定 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 埃氏筛法求欧拉函数值的表，每次发现质因子就把他的倍数的欧拉函数乘上 (p−1)×p当 n 为奇数时，有 ϕ(2n)=ϕ(n)因为 2n 是偶数，偶数与偶数一定不互素，所以只考虑 2n 与小于它的奇数互素的情况，则恰好就等于 nint 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,(b

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。