乘法逆元:若,则称
为
在
意义下的乘法逆元.
本文介绍乘法逆元的三种求法.
扩展欧几里得求逆元
因为,所以设
满足
,
则可以用扩展欧几里得求关于的方程
的一组解,即求出b.
inline int exgcd(int a,int b,int &x,int &y){ if(!b){ x=1;y=0;return a; } int ret=exgcd(b,a%b,y,x); y-=a/b*x;return ret; } inline int inver{ r=exgcd(a,p,b,q); if(r!=1) return -1; return b; }
费马小定理求逆元
因为,所以
,
则为a在
意义下的逆元.
typedef long long ll; inline ll power(ll x,ll k){ ll ret=1; while(k){ if(k&1) ret=ret*x%p; x=x*x%p;k>>=1; } return ret; } inline ll inver{ return power(a,p-2); }
线性求逆元
表示
在
(
为质数)意义下的逆元。
证明:因为,
所以
所以
所以
所以
typedef long long ll; inline ll inver{ re[1]=1; for(ll i=2,mul;i<=a;++i){ re[i]=-p/i*re[p%i]%p; if(re[i]<0){ mul=(0-re[i])/p+1; re[i]=(re[i]+mul*p)%p; } } return re[a]; }
原文：http://www.cnblogs.com/AireenYe/p/5929578.html