在开始之前我们先介绍3个定理:
1.乘法逆元(在维基百科中也叫倒数,当然是 mod p后的,其实就是倒数不是吗?):
如果ax≡1 (mod p),且gcd(a,p)=1(a与p互质),则称a关于模p的乘法逆元为x。
2.费马小定理(定义来自维基百科):
假如a是一个整数,p是一个质数,那么是p的倍数,可以表示为
如果a不是p的倍数,这个定理也可以写成
3.
扩展欧几里得
- (定义来自维基百科):
已知整数a、b,扩展欧几里得算法可以在求得a、b的最大公约数的同时,能找到整数x、y(其中一个很可能是负数),使它们满足贝祖等式。
好了,在明白上面的定理后我们开始分析乘法逆元:ax≡1 (mod p) 这个等式用中文描述就是 a乘一个数x并模p等于1,即 a%p*x%p=res,res%p=1;看上去就是同余定理的一个简单等式- -。那么问题来了。
为什么可以用费马小定理来求逆元呢?
由费马小定理 ap-1≡1 两边同时乘 ap-1得 ap-2≡ap-1,两边同时除 ap-1得 ap-2/ ap-1≡1, 变形得 aap-2≡1(mod p),答案已经很明显了:若a,p互质,因为aap-2≡1(mod p)且a*x≡1(mod p),则x=ap-2(mod p),用快速幂可快速求之。
为什么可以用扩展欧几里得求得逆元?
我们都知道模就是余数,比如12%3=12-12/3=1,18%2=18-18/5=3。(/是程序运算中的除)
那么ax≡1 (mod p)即ax-yp=1.把y写成+的形式就是ax+py=1,为方便理解下面我们把p写成b就是ax+by=1。就表示x是a的模b乘法逆元,y是b的模a乘法逆元。然后就可以用扩展欧几里得求了。
知道逆元怎么算之后,那么乘法逆元有什么用呢?
做题时如果结果过大一般都会让你模一个数,确保结果不是很大,而这个数一般是1e9+7,而且这个数又是个素数,加减乘与模运算的顺序交换不会影响结果,但是除法不行。有的题目要求结果mod一个大质数,如果原本的结果中有除法,比如除以a,那就可以乘以a的逆元替代。(除一个数等于乘它的倒数,虽然这里的逆元不完全是倒数,但可以这么理解,毕竟乘法逆元就是倒数的扩展)。
扩展欧几里得求逆元代码:
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 void exgcd(ll a,ll b,ll& d,ll& x,ll& y){
5 if(!b) { d = a; x = 1; y = 0; }
6 else{ exgcd(b, a%b, d, y, x); y -= x*(a/b); }
7 }
8 ll inv(ll a, ll p){
9 ll d,x,y;
10 exgcd(a,p,d,x,y);
11 return d == 1 ? (x+p)%p : -1;
12 }
13 int main()
14 {
15 ll a,p;
16 while(1){
17 scanf("%lld %lld",&a,&p);
18 printf("%lld\n",inv(a,p));
19 }
20 }
原文链接: https://www.cnblogs.com/suishiguang/p/6363968.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/248692
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!