引理：

缩系：

简单的定义：对于m(m>1)，在 [1,m] 区间中所有与 m 互素的数可以构成一个缩系。
缩系性质 1、缩系中必定每个元素都有自己唯一的逆元，并且每个元素的逆元不与其他元素的重复 (一一对应的关系)。
缩系性质 2、对于任意的与 n 互质的正整数 k，若 {A1,A2,…,Am} 为模 n 的一个缩系,(k,n)=1, 则 {kA1,kA2,…,kAm} 也为模 n 的一个缩系 .
缩系性质 3、由缩系性质１导出：$\Pi A_i = 1$

逆元的定义：

在 mod p 意义下，若 ab=1，那么 ab 互为对方的逆元。
定理一：在 mod p(p 为质数) 意义下，任意一个数 x(1<=x< p) 都有它的逆元
证明：首先 {1,2,…,p-1} 是一个缩系。(显然)
由缩系性质１：定理１成立。
定理二：在 mod q(q 不是质数) 意义下，如果 (a,q)==1(a 在 mod q 的缩系内)，a 有逆元。如果 (a,q)!=1, 那么 a 没有逆元
证明：(显然)
定理三：在 mod p 意义下，如果 ab=1, 那么 x/a=xb;
证明：因为 ab=1, 所以 1/a=b，所以 x(1/a)=xb

所以，如果 p 为质数，我们就可以放心地求 p 以内所有数的逆元。

逆元求法１：扩展欧几里德算法 (ap 互质)(lnn)

由于逆元的定义：xa=1(mod p)
所以我们可以用扩展欧几里德算法求出使 ax=1 的 x，xa+yp=1

int exgcd(int a, int b, int &x, int &y)//扩展 gcd
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int r = exgcd(b, a % b, x, y);
    int t = x % mod;
    x = y % mod;
    y = ((t - a / b * y) % mod + mod) % mod;
    return r;
}
int main()
{
    int a,inv,nt;
    cin>>a>>mod;
    exgcd(a,mod,inv,nt);
    cout<<inv<<endl;
}

逆元求法２：费马定理 (p 为质数,xp 互素)(logn)

费马定理：$x^{(p-1)}=1(mod p)$
证明：这里需要应用缩系的性质２、３。
令 $$s=x^{(p-1)}(p-1)!$$
那么 $$s=1x\times(2x)\times(3x)\times…\times((p-1)x)$$
由缩系性质 2: 这也是一个缩系的所有元素的积。因此 $s=1$
因为 (p-1)! 是一个缩系的所有元素的积，所以 (p-1)!=1
因此可以说明 $x^{(p-1)}$也为１时 s 才为１。
证毕

int ksm(int a,int mi)//快速幂
{
    int ans=1,t=a;
    while(mi>=1)
    {
        if(mi&1)ans*=t,ans%=mod;
        t*=t,t%=mod,mi/=2;
    }
    return ans;
}
int main()
{
    int a;
    cin>>a>>mod;
    cout<<ksm(a,mod-2);
}

逆元求法３：欧拉函数 (ap 互质)(sqrt(n))

欧拉定理：$a^{phi(p)} = 1 (mod p)$
证明：令 S 为 mod p 意义下缩系的元素之积，因此 S=1
那么：$a^{phi(p)}S=1$
证毕

int main()
{
    int a,mod;
    cin>>a>>mod;
    cout<<ksm(a,phi(mod)-1)<<endl;
}

逆元求法４：线性递推 (p 为质数)(平均每个 O(1))

首先证明 $i^{-1}=(pmod i)^{-1}(p-[\frac{p}{i}])$
证明：
$$p mod i = p – [\frac{p}{i}]i$$
$$p mod i = -[\frac{p}{i}]i$$
由于 $x/a=xa^{-1}$（其中 a^{-1} 为 a 的逆元），所以我们经过移项得：
$$i^{-1}=-[\frac{p}{i}](p mod i)^{-1}$$
也就是：
$$i^{-1}=(p-[\frac{p}{i}])(p mod i)^{-1}$$

int inv[1000];

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