【数论】费马小定理

有a和p，如果p是质数，那么：

a^(p - 1) % p = 1;

证明：

若n不能整除a - b，x>0，(x,n)=1，則n也不能整除x(a-b)。取整數集A为所有小於p的集（A构成p的完全剩余系,即A中不存在两个数同余p），B是A中所有的元素乘以a组成的集合。因为A中的任何两个元素之差都不能被p整除，所以B中的任何两个元素之差也不能被p整除。因此

1∗2∗3∗...∗(p−1)%p=a∗2a∗3a∗...∗a(p−1)形成了一个循环

1∗2∗3∗...∗(p−1)=w 且w和p互质，所以整个式子除以w之后得到a^(p - 1) % p= 1

应用：可以用来求指数循环节

也可以用来求逆元，逆元为a^(p - 2) % p;

这是由于a ^ (p - 1) % p = 1，等同于a * a ^ (p - 2) % p = 1，所以a ^ (p - 2) % p为逆元

long long pow(long long n, long long k) {
    if (k == 0) return 1;
    if (k == 1) return n;
    long long ans = pow(n * n % p, k>>1);
    if (k&1) ans = ans * n % p;
    return ans;
}

//调用 pow(a, p - 2) % p 求出逆元