（本篇并不适合初学者看）

1.定义：

如果a%m=b%m，则称a，b关于m同余，记作：a≡b mod m

2.费马小定理/欧拉定理

费马小定理：若p是质数，对于任何整数a，有a^p = a mod p

欧拉定理：若a，p互质，有a^phi(p) = 1 mod p

欧拉定理的推论：

a^b= a^(b mod phi (p)) mod p

支持了对指数取模。注意，如果预处理的组合数位于指数位置，要对phi(p)取模，而不是p

3.扩展欧几里得算法

裴属定理：存在x，y使得a*x+b*y=gcd(a,b)

证明：

欧几里得算法最后一步：b=0,a=gcd,显然x=1，y=0是一组x，y的解。

然后有：gcd(a,b)=gcd(b,a%b)

所以，a*x'+b*y'=b*x+(a%b)*y=b*x+(a-[a/b]*b)*y=a*y+(x-[a/b]*y)*b

所以，令x'=y,y'=(x-[a/b]*y)就是一组解。

根据数学归纳法，最后有解，然后可以往上构造。

所以，存在x，y

证毕。

也给出了x，y的求法。

扩展欧几里得就是干这个的。

4.乘法逆元

如果a，p互质，那么存在一个b，使得a*b=1 mod p

这个b就是a在mod p意义下的乘法逆元。记作a^(-1) mod p

于是，c/a=c*a^(-1) mod p

①求法：

01.扩展欧几里得。a*b+k*p=1。还证明了(a,p)=1才有逆元

10.费马小定理/欧拉定理。a^phi(p)=1 mod p，所以，inv(a)=a^(phi(p)-1) mod p

11.线性预处理逆元（基本没用过）

[p/i]*i+p%i=0 mod p

[p/i]*i=p-p%i mod p

-[p/i]*inv(p%i)*i=1 mod p

所以，inv[i]=(p-[p/i])*inv[p%i] mod p

 

可以支持除法的处理。

5.线性同余方程

1.ax=b mod p

即：ax+kp=b ，当gcd(a,p)|b时有解。（否则一边提不出来gcd）

扩欧即可。

2.

 

 许多个方程，中国剩余定理。

6.高次同余方程

 a^x=b mod p 求x（一般求最小解，可能无解）

一篇博客：

如果gcd(a,p)=1,BSGS算法。

可以得到a^phi(p)=1 mod p

那么，x如果有解，最小解一定小于等于phi(p)，否则根据a^b=a^(b mod phi(p)) mod p

就循环了。

对于ou=phi(p)分块,每块是根号ou上取整，记为blo。

设x=i*blo+j;(0<=j<blo)（0<=i<=blo）

那么，若a^(i*blo+j)=b mod p

则a^(i*blo)= b * inv(a^j) mod p

我们可以先枚举j，把b*inv(a^j) mod p 放进一个hash表里。

然后枚举i，判断a^(i*blo)在哈希表中有没有出现，

有的话，返回j，i*blo+j即为解。

如果(a,p)!=1呢？

 看博客吧。

 

总结：

同余这一部分，就解决了很多模意义下的运算。

1.我们可以灵活运用模意义下的加减乘除乘方运算。（除法，乘方mod，要保证互质）

这在快速幂，组合数问题中经常见到。

2.我们可以解线性同余方程（组）。

CRT在EXLUCAS中也有应用

3.高次同余方程入门，BSGS&&EXBSGS