欧几里得算法
费马小定理
当a,p都是是质数时,a^(p-1)=1(mod p)
证明：
举个例子 a=2,p=5;
1,2,3,4 集合（1） {1，2，3，4...,(p-1)}
2,4,6,8 => %5 => 2,4,1,3 集合（2） {1a%p,2a%p,3a%p,4a%p...,(p-1)a%p}
我们发现{1，2，3，4}和{2，4，1，3}只是位置不同，成积相同
怎么个一定乘积相同法？
反证法：
首先（1）一定不会有相同，（2）的证法如下
ai=aj (mod P) => a(i-j)=0 (mod p) => p|a(i-j) 这可能吗？p是质数
证毕
裴属定理
证明：c|ax,c|by，所以c|ax+by,证毕：）
求逆元（老重要了！！！）
- 扩展欧几里得算法
点击查看代码
void Exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) x = 1, y = 0;
else Exgcd(b, a % b, y, x), y -= a / b * x;
}
int main() {
ll x, y;
Exgcd (a, p, x, y);
x = (x % p + p) % p;
printf ("%d\n", x); //x是a在mod p下的逆元
}
- 线性方法
求i的逆元
点击查看代码
inv[1] = 1;
for(int i = 1; i < p; ++ i)
inv[i] = (p - p / i) * inv[p % i] % p;//这里有个问题困扰了我很久，为什么（p-p/i)=-(p/i) ? 因为 -(p/i)%p=p-(p/i) 不知道的去查
对与中国剩余定理
标签：ll,Exgcd,逆元,定理,数学知识,一些,inv,mod From： https://www.cnblogs.com/zjr20120321/p/18445888