关于逆元的学习笔记（尚未完成）

QwQ嘤嘤嘤 只是为了整理一下自己的求逆元的方法

假设我们要求a在模p意义下的逆元，我们会有以下几种做法：

1>如果p是质数的话 $$a^{p-1} equiv 1 pmod p $$

那么我们稍加变形，就能得出$$a^{p-2} equiv frac{1}{a} pmod p$$

那么(a^{p-2})就是逆元了
可以直接用快速幂求解

ll qsm(ll ii,ll j)
{
  ll ans=1;
  while (j)
  {
     if (j&1) ans=ans*i%mod;
     i=i*i%mod;
     j>>=1;
  }
  return ans;
}

int main()
{
    inv = qsm(a,p-2)
}

2.扩展欧几里得
求逆元，实际上就是求这个式子的x

[ax equiv 1 pmod p ]

然后解一下就好

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

3.线性求逆元

能够求出(1-n)所有数在(mod) p意义下的逆元

首先我们对于一个要求的数(i)来说

(p=k*i+r)
那么$$k*i+r equiv 0 pmod p $$

等式两边同时乘(i^{-1}*r^{-1})

则$$k*r^{-1}+i{-1}equiv 0 pmod p $$

[i^{-1}equiv -k*r^{-1} pmod p ]

又因为$k=lfloor frac{p}{i} floor，r=p % i $

所以$$i^{-1}equiv -lfloor frac{p}{i} floor*(pmod i)^{-1} pmod p$$

inv[1]=1;
  for (int i=2;i<=n;i++)
  {
  	 inv[i]=-(p/i)*inv[p%i];
  	 inv[i]=(inv[i]%p+p)%p;
  }