乘法逆元

乘法逆元作用：在+,-,*运算中求%可以分开对每一项取模再进行运算，但如果表达式中有除法就不行了。这时我们可以求出分母的乘法逆元。如：(9/3)%5=3%5=3,我们可以求出3的逆元2，则 (9/3)%5=9*inv(3)%5=9*2%5=3

注意：只有a与p互质时才存在乘法逆元.

下面是求a在%p下的逆元   ：扩展欧几里得法。

扩展欧几里得：已知a,b，求ax+by=gcd(a,b)=d中的d,x,y

而ax%p=1时即ax+1=py->ax+py=1

#include<bits/stdc++.h> using namespace std; typedef long long ll; void exgcd(ll a,ll b,ll& d,ll& x,ll& y)//已知a,b，求ax+by=gcd(a,b)=d中的d,x,y { if(!b) { d = a; x = 1; y = 0; } else{ exgcd(b, a%b, d, y, x); y -= x*(a/b); } } ll inv(ll a, ll p) { ll d, x, y; exgcd(a, p, d, x, y); return d == 1 ? (x+p)%p : -1; } int main() { //a在%p下的逆元 ,若a,p不互质，则不存在，返回-1 ll a,p; while(1) { scanf("%lld %lld",&a,&p); printf("%lld\n",inv(a,p)); } }

若p为素数，则可利用费马小定理：inv(x)=x^(p-2)%p算

ll quickPow(ll a,ll n,ll p) { ll ans=1; while(n) { if(n&1)ans=(ans*a)%p; a=(a*a)%p; n>>=1; } return ans; } ll inv(ll a,ll p) { return quickPower(a,p-2,p); }