求乘法逆元的几种方法

2019-04-13 17:07发布

(数学渣,下面的文字可能有误,欢迎指教)
乘法逆元的定义貌似是基于群给出的,比较简单地理解,可以说是倒数的概念的推广。记a的关于模p的逆元为a^-1,则a^-1满足aa^-1≡ 1(mod p)

加减乘与模运算的顺序交换不会影响结果,但是除法不行。有的题目要求结果mod一个大质数,如果原本的结果中有除法,比如除以a,那就可以乘以a的逆元替代。

在mod p的运算中,a存在乘法逆元当且仅当a与p互质。一般题目给的是一个大质数,所以只要a不是p的倍数,就以求乘法逆元。

目前了解到的求法有三种:
1.扩展欧几里得。aa^-1≡ 1(mod p),可以转换为aa^-1 + py = 1,即是扩展欧几里得所能解的ax + by = gcd(a, b)。最常用的解法。int x, y; int extgcd(int a, int b, int &x, int &y) { if (b == 0){ x = 1; y = 0; return a; } int gcd = exgcd(b, a % b, x, y); int tmp = x; x = y; y = tmp - (a/b) * y; return gcd; } /* 求解ax+by=gcd(a,b),亦即ax≡1(mod b)。函数返回值是a,b的最大公约数,而x即a的逆元。 注意a, b不能写反了。 */ 2.由费马小定理a^(p-1)≡ 1(mod p)(p为素数),稍作变形即是 aa^(p-2)≡ 1(mod p),是不是发现了,a^(p-2)即是a的逆元,这个可以用快速幂来求。 3.网上看到的一个很厉害的o(n)的递推,求前n个逆元,不知道是怎么推出来的,但是可以简单地证明一下正确性(要求所mod p为素数)。 首先,1的逆元是1,没什么疑问。
假设前i个数的逆元已经求出,那么
i^-1 = (p%i)^-1 * (p - [p/i]) % p。其中[]表示去尾取整。
(p%i)^-1其实就是(p-[p/i]i)^-1,然后我们左右乘以i,
ii^-1 = (p-[p/i]i)^-1 * ((i-1)p + p-[p/i]i) % p,
其实就是ii^-1 = k^-1 * ((i-1)p + k) % p = 0 + 1 = 1,这样就证完了=。= //字体真糟糕。。 int[] inv = new int[MAXN]; inv[1] = 1; for (int i = 2; i


今天我们来探讨逆元在ACM-ICPC竞赛中的应用,逆元是一个很重要的概念,必须学会使用它。   对于正整数,如果有,那么把这个同余方程中的最小正整数解叫做的逆元。   逆元一般用扩展欧几里得算法来求得,如果为素数,那么还可以根据费马小定理得到逆元为。   推导过程如下                                求现在来看一个逆元最常见问题,求如下表达式的值(已知                 当然这个经典的问题有很多方法,最常见的就是扩展欧几里得,如果是素数,还可以用费马小定理。   但是你会发现费马小定理和扩展欧几里得算法求逆元是有局限性的,它们都会要求互素。实际上我们还有一 种通用的求逆元方法,适合所有情况。公式如下                现在我们来证明它,已知,证明步骤如下              逆元详解:   http://blog.csdn.net/acdreamers/article/details/8220787