首页 > 代码库 > 乘法逆元
乘法逆元
模的运算规则
运算规则
模运算与基本四则运算有些相似，但是除法例外。其规则如下：
(a + b) % p = (a % p + b % p) % p （1）
(a - b) % p = (a % p - b % p) % p （2）
(a * b) % p = (a % p * b % p) % p （3）
(a^b) % p = ((a % p)^b) % p （4）
结合律：
((a+b) % p + c) % p = (a + (b+c) % p) % p （5）
((a*b) % p * c)% p = (a * b*c) % p （6）// (a%p*b)%p=(a*b)%p
交换律：
(a + b) % p = (b+a) % p （7）
(a * b) % p = (b * a) % p （8）
分配律：
((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p （9）
重要定理：
若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；（10）
若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)；（11）
若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，
(a * c) ≡ (b * d) (%p)，(a / c) ≡ (b / d) (%p)； （12）
乘法逆元：
定义： 满足a*k≡1 (mod p)的k值就是a关于p的乘法逆元。
为什么要有乘法逆元呢？
当我们要求（a/b） mod p的值，且a很大，无法直接求得a/b的值时，我们就要用到乘法逆元。 我们可以通过求b关于p的乘法逆元k，将a乘上k再模p，
即(a*k) mod p。其结果与(a/b) mod p等价。
证：（其实很简单。。。） 根据b*k≡1 (mod p)有b*k=p*x+1。 k=(p*x+1)/b。
把k代入(a*k) mod p，得：
(a*(p*x+1)/b) mod p =((a*p*x)/b+a/b) mod p
=[((a*p*x)/b) mod p +(a/b)] mod p
=[(p*(a*x)/b) mod p +(a/b)] mod p
//p*[(a*x)/b] mod p=0
所以原式等于：(a/b) mod p
在计算一个很大的组合数modP时会用到乘法逆元。即把/a变成*(f(a))，其中f(a)为a在模P意义下的乘法逆元，即a*f(a) mod P=1计算乘法逆元有两种方法，扩展gcd或基于欧拉公式的快速幂取模。------------------------------------------------------------------------------------------------------扩展gcd就是求解方程ax=1(mod P)的最小整数解.设ax=1+y*p，即a*f(a,p)=1+p*g(a,p)，把x和y的解看成关于a,p的函数。a>=p时，设a=p*k+r，则式子变成：p*k*f(a,p)+r*f(a,p)=1+p*g(a,p)，移项，得r*f(a,p)=1+p*(g(a,p)-k*f(a,p))那么就得到f(a mod p,p)=f(a,p)，g(a mod p,p)=g(a,p)-[a/p]*f(a,p);p>=a时差不多一个意思。所以把f,g设成全局变量，像普通gcd那样做，即时更新f,g即可。----------------------------------------------------------------------------------------------------设欧拉函数phi(x)=在[1,x-1]中与x互质的数字个数。那么欧拉公式：a^phi(P)=1(mod P)两边同除a,即可得到a^(phi(P)-1) mod P即为a在模P意义下的乘法逆元。特例：
如果P是质数，那么phi(P)=P-1.即a的乘法逆元为a^(P-2)，快速幂即可。
#include <iostream>using namespace std;int extended_gcd(int a,int b, int &x, int &y){ if (b == 0) { x = 1; y = 0; return a; } else { int gcd = extended_gcd(b, a % b, x, y); int t=x%mod; x=y%mod; y=((t-a/b*x)%mod+mod)%mod; return gcd; }}int main(){ int i, x, y; const int P = 13; for (i = 1; i < P; ++i) { extended_gcd(i, P, x, y); while (x < 0) x += P; printf("1 div %d = %d\n", i, x); } return 0;}
乘法逆元
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。