同余：
概念：
整数a mod 整数b，得到正余数为c。
c±kb(k为自然数)均为a除以b的余数，属同余系。
一般写为ax≡b(mod c) ("≡"打法:Alt+小键盘的41428)
而同余理论创立者则是高斯！
接下来我们进一步了解同余的性质：
（1）两数的和（或差）于他们余数的和（或差）同余数。简而言之：(a±b)%c=(a%c)±(b%c);
（2）两数的乘积与他们余数的乘积同余。简而言之：(a*b)%c=(a%c)*(b%c);
（3）如果两个整数同余，那么他们的差就一定能被这个数整除。简而言之：当a≡b(mod c)，a-b=±k*c(k为整数)
（4）如果两个整数同余，那么他们的乘方仍然同余。简而言之：当a≡b(mod c)，a^k≡b^k(mod c)
(5) 若ak≡bk（mod c），gcd（k，c）=1，那么a≡b（mod c)。
逆元：
在做题中，我们常常会要处理、储存超long long、int的数据，这时只能扣高精……但是现在越来越多题输出%mod的答案，这意味我们可以用同余的性质(1)、(2)在中间处理，不会超long long、int等！
但是我们发现但如果遇到（a/b）%mod时怎么办？也许有人说:（a/b）%mod=(a%mod)/(b%mod)!!!
这究竟对不对呢？我们手推个例子：(20\4)%2，如果按上述就成:0/0，这就奇怪了！那我们遇到一个很大的a、b怎么办（尤其组合数学！）？
于是引出重点——逆元
设a-1为a的逆元，a-1*a≡1(mod p) 所以当两边除a时，等于乘其逆元
如果a=3，p=7，我们枚举出a-1=5，因为5*3≡1（mod 7）！
时间为O（p）
解释:我们可发现a-1=k1*p+k2,(k1=floor(a-1/p))
k1*p+k2*a≡1(mod p)
k2*a≡1(mod p) ——因为k1*p mod p=0,由性质(1)
而k2小于p,所以最大时间O(p)
这是也许会不解:逆元怎么用?
它可以用来解同余方程:kx+c=0(mod p)(k、c为整数，求x)
移项:kx≡-c(mod p)
带入逆元:x≡-c*k-1(mod p)
求出k的逆元即可解！
我们有什么办法快速求逆元：
1、费马小定理：
在p为质数时，a(p-1)≡1(mod p),所以a-1≡a(p-2)
引入的证明：
- 引理1:
当 p为质数且 c 为整数,由 ac≡bc(mod p) 可推出 a≡b(mod p)
ac≡bc(mod p)→ac−bc≡0(mod p)→c(a−b)≡0(mod p)
所以 c(a−b)是 p 的整数倍。
因为 p 为素数,所以 c,p 互质。
即 (a−b) 是 p 的整数倍。
即 a−b≡0(mod p)→a≡b(mod p)
- 证明
默认 p 为质数。
取集合 T1{1,2,3,...,p−1} 这 p−1 个数,他们的积为 (p−1)!
然后,将 {1,2,3,...,p−1} 同乘 a ,其中 a 是一个正整数( p 的同余系下)
得集合 T2{a,2a,3a,...,(p−1)a}
假设这些数中有两个相同:
得 k1a=k2a(mod p)其中 k1,k2∈T1且 k1≠k2 。
然而根据引理1, k1=k2,矛盾,假设不成立。
即设这些数各不相同。
假设这些数中有某个为0
得 ka=0(mod p),其中 k>0,a>0
由假设得 ka 是 p的整数倍。
然而 k,a和 p 互质,矛盾,假设不成立。
故集合 T2 中的数各不相同,且不为0,那么 T2=T1={1,2,3,...,p−1} (由于同余系的缘故)
我们把 T2 里面的所有数乘在一起,得到 a(p−1)∗(p−1)!
因为 T1==T2 所以对应积相等,即 a(p−1)∗(p−1)! ≡ (p−1)! (mod p)
因为 (p−1)! 与 p 互质( p 是素数)
所以 a(p−1)≡1(mod p)
2、扩欧：
扩欧即扩展欧几里得(即exgcd)
未学欧几里得算法的跳过
附上
#include#include using namespace std;long long gcd(long long a,long long b){ if (!b)return a; return gcd(b,a%b);}int main(){ long long a,b,x,y,ok; scanf("%lld %lld",&a,&b); printf("%lld\n",gcd(a,b)); return 0;}
求ax+by≡gcd(a,b)的一组解(a,b已知):
由欧几里得的gcd(a,b)=gcd(b,a%b)
假设a1=b,b1=a%b,且已知a1*x+b1*y≡gcd(a,c)的x1,y1
带入原式:b*x1+(a%b)*y1≡gcd(a,b)
b*x1+(a-b*floor(a/b))*y1≡gcd(a,b)
b*x1+a*y1-b*floor(a/b)*y1≡gcd(a,b)
ay1+b(x1-floor(a/b)*y1)≡gcd(a,b)
所以可以通过x1,y1求出x,y, x=y1 y=x1-floor(a/b)*y1
这时发现我们可以不断向下调用，直到b=0，式子变成ax≡a，这时x=1，y=0可以为特解！！！（类似欧几里得）,这时可以解之前的方程！时间复杂度和欧几里得一样，为（log）
接下来，我们怎么把其代入求逆元？ 我们的方程组：ax+by=gcd(a,b) 两边同模b
--> ax+by≡gcd(a,b)(mod b) 因为by mod b=0
-->ax≡gcd(a,b)
-->由裴蜀定理得方程 ax + by = 1 有解当且仅当整数a和b互素,所以当a、b互质时,a^-1为x,否则无解!
因为欧几里得不是在同余系中，所以x有可能是负数！！！
#include#include using namespace std;long long exgcd(long long a,long long b,long long &x,long long &y){ if (!b){ x=1; y=0; return a; } else { long long ans=exgcd(b,a%b,x,y); long long z=x; x=y; y=z-a/b*y; return ans; }}int main(){ long long a,b,x,y,ok; scanf("%lld %lld",&a,&b); if (exgcd(a,b,x,y)==1) { printf("%lld\n",(x+b)%b); } return 0;}
证明裴蜀定理:设存在x，y使ax+by=d，d是ax+by取值中的最小正整数，d≠1。再设am+bn=e，则e≥d .若d不整除e，对e做带余除法.必定存在p，r使e=pd+r.r＜d则r=e-pd=（m-px）a+（n-py）b.存在整数m-px，n-py使ax+by=r＜d，与d的最小性矛盾。所以d整除e.令m=1，n=0，则d整除a；同理d整除b.所以d=(a,b).a,b互质时，d=1(来源)
3、大佬的
膜拜大佬！！！O（n）算法！！！
设现在求i的逆元，且1~i-1的逆元已求出。设a=floor(p/i)，b=p%i，得a*i+b≡0(mod p)
-->移项:-a*i≡b(mod p)
-->两边乘i-1*b-1,得-a*b-1≡i-1(mod p)
因为b<p，所以i^-1≡-floor(p/i)*(p%i)^-1!!!
因为-floor(p/i)为负数,i-1≡(p-floor(p/i))*(p%i)-1!!!
注意边界：1-1≡1(mod p)，将其做边界！
4、欧拉定理
……更多（欧拉等）……
推荐读物（适合数论初学者）：《初等数论及其应用》！