乘法逆元

• 快速幂求逆元 时间复杂度：\(O(\log p)\)

ll qow(ll x,ll y)
{
	ll res=1;
	while(y>0)
	{
		if(y&1)(res*=x)%=p;
		(x*=x)%=p;y>>=1;
	}
	return res;
}

• 扩展欧几里得求逆元 时间复杂度\(O(\log p)\)
  证明：
  \(ax+py=1两边同时模p\)
  \(ax\%p+py\%p=1\%p\)
  \(ax\%p=1\%p\)
  \(ax\equiv1\pmod{p}\)
  所以同理可以证得\(ax+py=1的一组解(x,y)，x 是a关于p的逆元，y是p关于a的逆元\)

void exgcd(int a, int b, int& x, int& y) {
  if (b == 0) {
    x = 1, y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= a / b * x;
}

• 线性求逆元（连续逆元）时间复杂度：\(O(n)\)
  证明：
  \(对于递归情况i^{-1}，令k=\left\lfloor \frac{p}{i}\right\rfloor,j=p \mod i,有p=ki+j。在\mod p意义下会得到：{ki+j}\equiv0\pmod{p}\)
  两边同时乘\(i^{-1}*j^{-1}\)
  \(kj^{-1}+i^{-1}\equiv0\pmod{p}\)
  \(i^{-1}\equiv{-kj^{-1}}\pmod{p}\)
  \(i^{-1}\equiv{-\left\lfloor \frac{p}{i}\right\rfloor (p\%i)^{-1}}\pmod{p}\)
  ps:用\(p-\left\lfloor \frac{p}{i}\right\rfloor来防止负数\)

for(int i=1;i<=n;i++)
{
	if(i==1)lv[i]=1;
	else lv[i]=(p-p/i)*lv[p%i]%p;
	printf("%lld\n",lv[i]);
}

• 线性求逆元（n个数）时间复杂度：\(O(n+\log p)\)
  计算n个数的前缀积，记为\(s_i\)，然后使用快速幂或扩展欧几里得计算\(s_n\)的逆元，记为\(sv_n\)。
  因为\(sv_n\)是n个数的积的逆元，所以当我们把它乘上\(a_n\)时，就会和\(a_n\)的逆元抵消，于是就得到了\(a_1\)到\(a_{n-1}\)的积逆元，记为\(sv_n\)。
  同理我们可以依次计算出所有的\(sv_i\)，于是\(a_i^{-1}\)就可以用\(s_{i-1}*sv_i\)求得。

s[0]=1;
for(int i=1;i<=n;i++)s[i]=s[i-1]*a[i]%p;
lv[n]=qow(s[n],p-2);//快速幂
for(int i=n;i>=1;i--)lv[i-1]=lv[i]*a[i]%p;
for(int i=1;i<=n;i++)printf("%lld\n",s[i-1]*lv[i]%p);

原文地址：http://www.cnblogs.com/mkik/p/16851796.html