看数论看得头皮发麻，o(╥﹏╥)o，总算理解了一些东西。（推荐一个dalao博客，个人感觉他的博客易懂点，可能是那些颜文字的作用（逃...））
在看逆元之前我们先来看个同余方程的定理吧
同余定理：a和b取余p得到相同的余数，a≡b(mod p) 等价于 （a-b）/p得到一个整数。（其实个人感觉写成 （a mod p）≡（b mod p） 更好理解）
逆元（数论倒数）：对于正整数a和p，如果有ax≡1（mod p），那么把这个同余方程中x的最小正整数解称为a mod p的逆元。
为什么叫数论倒数呢，因为没有mod操作，那么x就相当于a的倒数，有mod操作时效果上和倒数一样。
同时我们把a的逆元写做：inv（a）
求解逆元：
1.费马小定理：a^(p-1) ≡1 (mod p)
两边同时除以a，a^(p-2) ≡inv（a）(mod p)。即inv（a）≡a^(p-2)(mod p)
1 typedef long long LL;
2 LL fast_mod(LL x,LL n,LL mod){
3 LL ans=1;
4 while(n>0){
5 if(n&1) ans=(ans*x)%mod;
6 x=(x*x)%mod;
7 n>>=1;
8 }
9 return ans;
10 }
11 LL Fermat(LL a,LL b){
12 return fast_mod(a,p-2,p);
13 }
2.扩展欧几里得：a*x + b*y = 1
解x就是a关于b的逆元，解y就是b关于a的逆元
a*x % b + b*y % b = 1 % b
a*x % b = 1 % b
a*x = 1 (mod b)
1 typedef long long LL;
2 LL e_gcd(LL a,LL b,LL &x,LL &y){
3 LL d=a;
4 if(b!=0){
5 d=e_gcd(b,a%b,y,x);
6 y-=(a/b)*x;
7 }
8 else{x=1;y=0;}
9 return d;
10 }
11
12 LL inv(LL t,LL p){
13 LL x,y;
14 if(e_gcd(t,p,x,y)==1) return (x%p+p)%p;
15 else return -1;
16 }
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有 
