2018-03-17 12:06:26

还有一个半小时就开始天梯赛排位赛了 一个小时 看看求逆元吧 在补zoj2018三月赛C题的时候遇到的 之前遇见数学题基本上都是选择性略过的

感谢http://blog.csdn.net/guhaiteng/article/details/52123385

四种办法 例如 a/b%p 总结一下求逆元的适用情况 （是否要求a、b互质  是否要求p为质数  数据多大的时候可以用）  时间复杂度

这里不讲原理 原理原博客介绍的很详细 只讲应用

逆元存在的充分必要条件是a p互质

逆元的含义 在模n意义下 一个数a如果有逆元x 那么除以a相当于乘以x

一. 扩展欧几里得

不要求p为质数

效率较高 常熟较小 时间复杂度ln n 

typedef  long long ll;  void extgcd(ll a,ll b,ll& d,ll& x,ll& y){      if(!b){ d=a; x=1; y=0;}      else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }  }  ll inverse(ll a,ll n){      ll d,x,y;      extgcd(a,n,d,x,y);      return d==1?(x+n)%n:-1;  }

　　

二. 费马小定理

时间复杂度log2n 常数上比上一种办法大 几乎很少会用费马小定理求逆元

typedef  long long ll;  ll pow_mod(ll x, ll n, ll mod){      ll res=1;      while(n>0){          if(n&1)res=res*x%mod;          x=x*x%mod;          n>>=1;      }      return res;  }

 三. 求逆元的一般公式

上两种办法都要求a与p互质 

这种办法不要求互不互质  但是当a与p互质的时候b*p可能会很大 因此就需要用前两种办法来解决  不互质的时候考虑这种办法 效率较高

ans = (amodp*b)/b

四. 逆元打表

这种办法适用于求一个范围内所有数字的逆元

有一个递推公式

typedef  long long ll;  const int N = 1e5 + 5;  int inv[N];     void inverse(int n, int p) {      inv[1] = 1;      for (int i=2; i<=n; ++i) {          inv[i] = (ll) (p - p / i) * inv[p%i] % p;      }  }

之前对于分数取模也一直不理解 后面学习了这个发现 分数取模其实就是a*(b在p下的逆元)%p