逆元

用逆元求解是数论中常用的一种方法。

如果有数a,p，并有ax=1(mod p)，那么x称为模p意义下a的逆元。（显然的gcd(a,p)=1）

逆元常用的地方就是：求A/B(mod p)就等于A*x(mod p) x是模p意义下B的逆元.

求逆元的方法：

1.扩展欧几里得:

求得的x满足ax+py=gcd(a,p)(mod p)，所以满足ax=1(mod p)。

1 void e_gcd(int a,int b,int &x,int &y){
2     if (b==0){
3         x=1; y=0; return;
4     }
5     e_gcd(b,a%b,x,y);
6     int t=x; x=y;
7     y=t-(a/b)*y; 
8 }

View Code

用法：e_gcd(a,p,x,y); x即是逆元。

2.费马小定理：

要求：p为质数。

定理：A^(p-1)=1(mod p)。所以A^(p-2)即为逆元。

1 #define ll long long
2 ll powmod(ll a,ll b,ll pp){
3    ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;
4 }

View Code

用法：powmod(a,p-2,p)即为逆元；

3.欧拉定理：

a^phi(p)=1(mod p) 。所以A^(phi(p)-1)即为逆元。

由于这种做法在OI中不常用，仅供了解。