同余相关
xiejinhao
2019-07-06 13:57:42
# 同余
- **定义**
$ \ \ \ \ \ \ \ \ $ 若整数$a$和整数$b$除以正整数$m$的余数相等，则称$a,b$模$m$同余，记为$a \equiv b \pmod m$。
- **相关性质：**
1. $a \equiv a \pmod m$。
1. 若$ \ a \equiv b \pmod m$，则$ \ b \equiv a \pmod m$。
1. 若$ \ a \equiv b \pmod m,\ \ b \equiv c \pmod m \ $则$ \ a \equiv c \pmod m$。
1. 若$ \ a \equiv b \pmod m, \ c \equiv d \pmod m \ $，则$ \ a±c \equiv b±d \pmod m$。
1. 若$ \ a \equiv b \pmod m, \ c \equiv d \pmod m \ $，则$ \ ac \equiv bd \pmod m$。
1. 若$ \ ac \equiv bc \pmod m, \ c≠0$，则$ \ a \equiv b \pmod {m/gcd(c,m)}$；当$c,m$互质时，即$gcd(c,m)=1$，有$ \ a \equiv b \pmod m$。
1. 若$ \ a \equiv b \pmod m \ $，则$ \ a^n \equiv b^n \pmod m$。
1. 若$ \ a \equiv b \pmod {m_i}, \ i=1,2,…,n \ $，则$ \ a \equiv b \pmod {lcm(m_1,m_2,…,m_n)}$。特别的，若 $m_1,m_2,…,m_n$ 互质，则$a\equiv b \pmod{\prod \limits _{i=1}^{n}m_i}$。
- **同余类与剩余系：**
$ \ \ \ \ \ \ \ \ $ 对于$∀a∈[0,m-1]$，集合$\{a+km\}(k∈Z)$的所有数模$m$同余，余数都是$a$，则称该集合为一个模$m$的同余类，记为$\ \bar{a}$。
$ \ \ \ \ \ \ \ \ $ 模$m$的同余类一共有$m$个，分别记为$\bar{0}, \ \bar{1}, \ \bar{2},…,\bar{m-1}$。它们构成$\ m \ $的完全剩余系。
$ \ \ \ \ \ \ \ \ $ $1-m$中与$ \ m \ $互质的数代表的同余类共有$φ(m)$个，他们构成$ \ m \ $的简化剩余系。
- **费马小定理：**
$ \ \ \ \ \ \ \ \ $ 若$\ p \ $是质数，则对于任意整数$a$，有$a^p \equiv a \pmod m$。
- **欧拉定理：**
$ \ \ \ \ \ \ \ \ $ 若正整数$ \ a,n \ $互质，则$ \ a^{φ(n)} \equiv 1 \pmod n$
- **※欧拉定理相关：**
$ \ \ \ \ \ \ \ \ $ 若正整数$ \ a,n \ $互质，则对于任意正整数$ \ b \ $，有$ \ a^{b} \equiv a^{b \mod φ(n)} \pmod n$
- **威尔逊定理：**
$ \ \ \ \ \ \ \ \ $当且仅当$p$为质数时，$(p-1)!\equiv -1\pmod p$。
------------
同余相关 | 扩展欧几里得算法(扩欧)
------------
- $Bézout$ **定理：**
$ \ \ \ \ \ \ \ \ $ 对于任意整数$a,b$，存在一对整数$x,y$，满足 $ax+by=gcd(a,b)$。
$ \ \ \ \ $**证明：**
1. 在欧几里得算法的最后一步，有$b=0$，一定存在一对整数$x=1,y=0$，满足$a*1+0*0=gcd(a,0)=a$。
1. 若$b>0$，则$ \ gcd(a,b)=gcd(b,a\mod b)$。假设存在一对整数$ \ x,y$，满足$ \ bx+ (a \mod b)y=gcd(b,a \mod b)$，则$ \ bx+(a \mod b)y=bx+(a-b$⌊$a/b$⌋$)y=ay+b(x-$⌊$a/b$⌋$y)$。
1. 令$x_{'}=y,y_{'}=x-$⌊$a/b$⌋$y$，则$ax_{'}+by_{'}=gcd(a,b)$.
$ \ \ \ \ $对欧几里得算法运用数学归纳法，则 **$Bézout$ 定理** 成立。
$ \ \ \ \ $**证毕。**
由于 **$Bézout$ 定理**是按欧几里得算法证明的，上述证明又给出了计算上述方程的一组特解$x,y$的方法。这就是**扩展欧几里得算法**。
```cpp
int exgcd(int a, int b, int &x, int &y) {
if(b == 0) {x = 1, y = 0; return a;}
int d = exgcd(b, a%b, x, y);
int z = x; x = y, y = z - y * (a / b);
return d;
}
```
上述算法在范围$a,b$的最大公约数的同是，求出了一组特解$x_0,y_0$。
对于$ax+by=c$，其有整数解当且仅当$d|c$。我们可以利用上述算法先求出$ax+by=d$的一组特解$x_0,y_0$，然后同时将$x_0,y_0$同时乘上$\frac{c}{d}$，就得到了方程$ax+by=c,d|c$的一组特解。
方程$ax+by=c$的通解可以表示为：
$$x=\frac{c}{d}x_0+k\frac{b}{d}, \ \ \ \ y=\frac{c}{d}y_0+k\frac{a}{d}, \ \ \ k∈Z,d=gcd(a,b)$$
- **乘法逆元：**
$ \ \ \ \ $若整数$b,m$互质，并且$b|a$，则此存在一个整数$x$，使得$a/b \equiv ax \pmod m$。我们把$x$叫做$b$模$m$的乘法逆元，记作$b^{-1}\pmod m$。
上面那段定义来自于《算法竞赛进阶指南》，其实可以简述为存在一个$x$，使互质的$b,m$两个整数满足 $b*x \equiv 1 \pmod m $，其算式等价于$bx=km+1,\ \ \ b,k,m,x∈Z$，求$k,x$。
若$m∈prime$，根据费马小定理：$b^{m-1}\equiv1\pmod m$，则有$b*b^{m-2}\equiv1\pmod m$，此时$b^{m-2}$即为$b$模$m$的乘法逆元。
**乘法逆元的应用：**
对于第一个定义，题目要求取模运算时，一般会给定一个质数$p$,当然不是也不要紧，在处理$a/b \mod p$这样的式子时，保证$b,p$互质，则有且仅有一个$x$满足$a/b \mod p=a*x \mod p$，这时，$a/b \mod p=(a \mod p)(x \mod p)\mod p$ 。
------------
同余方程
------------
### **1.线性同余方程**
线性同余方程形如$ax \equiv b \pmod m$，求整数$x$或输出无解，这一类同余方程的指数为1，称为一次同余方程，也称线性同余方程。
上述方程等价于$ax-b \mod m =0$，不妨设$ax-b=-ym$，则有$ax+ym=b$，根据扩展欧几里得，我们可以求出方程$ax+ym=gcd(a,b)=d$的一组特解$x_0,y_0$。
根据 **$Bézout$ 定理**，方程有解当且仅当$gcd(a,m)|b$。
上面提到了这一类方程的解法，求出特解$x_0$后，方程的一个特解$x=x_0*\frac{b}{d}$。
**方程通解**：所有模$m/gcd(a,m)$与$x_0$同余的整数，表示为$X_i \equiv x_0 \pmod{m/gcd(a,m)}, \ \ \ i=1,2,…$。
- **例题**：[**P1082 同余方程**](https://www.luogu.org/problemnew/show/P1082)
由上述知识可得$ax \equiv 1\pmod b$可变为$ax+by=1$，利用欧几里得算法可以解出一组特解$x_0,y_0$，而$x_0$就是原方程的一个解，根据方程通解，利用模运算找到$[1,b]$的整数$x$，就是最小正整数解。
```cpp
//部分代码如下
typedef long long ll;
int exgcd(ll a, ll b, ll &x, ll &y) {
if(b == 0) {x = 1, y = 0; return a;}
ll d = exgcd(b, a%b, x, y);
ll z = x; x = y, y = z - y * (a / b);
return d;
}
int main() {
ll a, b, x=0, y=0;
scanf("%lld %lld", &a, &b);
exgcd(a, b, x, y);
printf("%lld\n",(x % b + b) % b);
}
```
- **中国剩余定理($CRT$)**
$ \ \ \ \ \ \ \ $设$m_1,m_2,…,m_n$是两两互质的整数，$m=\prod_{i=1}^{n}m_i, \ \ M_i=m/m_i, \ \ t_i$是线性同余方程$M_it_i\equiv 1 \pmod {m_i}$的一个解。对于任意的$n$个整数$a_1,a_2,…,a_n$，方程组
$$\begin{cases} { \ x \equiv a_1\pmod {m_1}} \\\ {x \equiv a_2\pmod {m_2}} \\\ {\ \ \ \ \ \ \ \ \ \ \ ...}\\\ {x \equiv a_n\pmod{m_n}} \end{cases}$$
$ \ \ \ \ \ \ \ $有整数解，解为$ \ x=\sum_{i=1}^{n}a_iM_it_i$。
$ \ \ \ \ \ \ \ $我们已经会解形如$ax \equiv 1\pmod m$的线性同余方程，因此，我们可以求解出$M_it_i\equiv 1 \pmod m$中的最小非负整数$t_i$，而方程的通解则为$x + i * M, \ \ \ i∈Z$。
```cpp
#include<cstdio>
using namespace std;
const int SIZE = 110;
int n, M = 1, a[SIZE], m[SIZE];
void exgcd(int a, int b ,int &x, int &y) {
if(b == 0) { x = 1, y = 0; return; }
exgcd(b, a % b, x, y);
int z = x; x = y, y = z - y * (a / b);
}
int CRT() {
int sum = 0;
for(int i = 1; i <= n; i++) M *= m[i];
for(int i = 1; i <= n; i++) {
int Mi = M / m[i];
int ti = 0, y = 0;
exgcd(Mi, m[i], ti, y);
ti = (ti % m[i] + m[i]) % m[i];
sum = (sum + a[i] * Mi * ti) % M;
}
return (sum + M) % M;
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d %d", &a[i], &m[i]);
printf("%d", CRT());
return 0;
}
```
$ \ \ \ \ \ \ \ $上面程序解出方程组的最小非负整数解。
- **扩展中国剩余定理($EXCRT$)**
$ \ \ \ \ \ \ \ $由基础的$CRT$我们已经会求解上述方程组。现在，由于方程组：
$$\begin{cases} { \ x \equiv a_1\pmod {m_1}} \\\ {x \equiv a_2\pmod {m_2}} \\\ {\ \ \ \ \ \ \ \ \ \ \ ...}\\\ {x \equiv a_n\pmod{m_n}} \end{cases}$$
$ \ \ \ \ \ \ \ $其中$m_1,m_2,…,m_n$为**不一定两两互质的整数**，求$x$的最小非负整数解。
$ \ \ \ \ \ \ \ $与$CRT$不同的是，这里的 $m_i$ 不一定两两互质。
$ \ \ \ \ \ \ \ $设前 $n - 1$个方程的一个解为 $x$，令$M=\prod_{i =1}^{n-1}m_i$，则前 $n-1$ 个方程的通解为 $x +i*M , \ \ \ i∈Z$。
$ \ \ \ \ \ \ \ $则对于整个方程组，就是要求解一个整数$k$使得$x + k*M\equiv a_n\pmod {m_n}$
$ \ \ \ \ \ \ \ $上述式子可转化为$k*M \equiv a_n-x\pmod{m_n}$，这也是我们熟悉的形如$ax\equiv b\pmod m$的线性同余方程，则上述方程有解，当且仅当$gcd(M,m_n) \mid (a_n-x)$，解为$k$。我们仍可以利用扩展欧几里得算法求解方程，则方程组的解就是$x+k*M$。
$ \ \ \ \ \ \ \ $因此，我们只需要使用$n$次扩展欧几里得算法，就可以求出整个方程的最小正整数解。
```cpp
#include<cstdio>
using namespace std;
const int SIZE = 1e5 + 10;
typedef long long ll;
typedef long double ld;
ll a[SIZE], m[SIZE];
ll quick_mul(ll x, ll y, ll p) { //x * y mod p
return
(x * y - (ll)((ld)x / p * y) * p + p) % p;
}
//由于这里需要用到gcd来判断是否有界，故需要返回值
ll exgcd(ll a, ll b, ll &x, ll &y) {
if(b == 0) { x = 1, y = 0; return a;}
ll d = exgcd(b, a % b, x, y);
ll z = x; x = y, y = z - y * (a / b);
return d;
}
ll EXCRT(int n) {
ll M = m[1], ans = a[1]; //x ≡ a[i] (mod m[i])
for(int i = 2; i <= n; i++) {
ll s = ((a[i] - ans) % m[i] + m[i]) % m[i];
//s = a[i] - x
ll x = 0, y = 0, d = exgcd(M, m[i], x, y);
// M*x ≡ 1 (mod m[i]),x相当于要求的k
if(s % d) return -1; //无解
x = quick_mul(x, s / d, m[i] / d);
ans += x * M;
M *= m[i]/d;
ans = (ans % M + M) % M;
//利用模性质,求最正整数小解
}
return (ans % M + M) % M;//返回最小正整数解
}
int main() {
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%lld %lld", a + i, m + i);
printf("%lld", EXCRT(n));
return 0;
}
```
------------
### **2.非线性同余方程 | 高次同余方程**
$ \ \ \ \ $ **①形如$x^a \equiv b \pmod m$的一类方程**
为什么现讲这一类？因为这一类是急需补充的知识，在一些算法书上基本没有。
那么，要解这一类方程，我们需要知道下面几个知识点：
- **阶：**
设$a,m∈Z, \ \ gcd(a,m) = 1$，则使方程$a^r \equiv 1 \pmod m$ 成立的最小正整数$ \ r \ $称为$a$对模$m$的阶，记为$r=ord_m(a)$，也记为$ \ δ_m(a)$。
**阶的基本性质：**
1. $a^n \equiv 1 \pmod m$的充要条件是$ \ δ_m(a) \ | \ n$
$ \ \ \ \ \ \ \ \ \ \ \ $ **推论**：$δ_m(a)|φ(m)$
**※** **若$δ_m(a)=φ(m)$，则称$a$是模$m$的原根(或写作元根)。**
2. 若 $a \equiv b \pmod m, \ \ gcd(a,m)=1$，则$δ_m(a)=δ_m(b)$。
1. 若 $a^x \equiv a^b \pmod m, \ \ gcd(a,m)=1$，则$x \equiv y \pmod {δ_m(a)}$。
1. 记$n=δ_m(a)$，则$a^1,a^2,…,a^{n-1}$模$m$两两不同余。
1. 若 $a^{-1}a \equiv 1\pmod m$，则$δ_m(a)=δ_m(a^{-1})$。
1. 记$n=δ_m(a), \ \ i=1,2,…, \ \ δ_m(a^i)=S$，则$S=n/gcd(i,n)$。
1. 若 $n \ | \ m$，则对于$∀a∈Z, \ \ \ δ_n(a) \ | \ δ_m(a)$。
1. 若$gcd(m,n)=1, \ gcd(a,mn)=1$，则$δ_{mn}(a)=[ δ_m(a),δ_n(a) ]$。
1. 若$gcd(ab,m)=1, \ gcd(δ_m(a),δ_m(b))=1$，则$δ_m(ab)=δ_m(a)*δ_m(b)$。
- **原根**
原根的定义在上面已经阐明，下面主要看**原根的性质：**
1. 只有$2,4,p^k,2p^k$有原根，其中$p$为奇素数，$k∈N^*$。
1. 一个数$x$若存在原根，则它有$φ(φ(x))$个原根。
1. 记$n=δ_m(a)$，当$n$为原根时，$\bar{a^0},\bar {a^1},\bar{a^2},…,\overline {a^{n-1}}$构成模$n$的简化剩余系。当$n$是质数时$\bar{a^0},\bar {a^1},\bar{a^2},…,\overline {a^{n-1}}$对$n$取模对应的值为{$1,2,…,n-1$}。
- **指标**
设$g$为$n$的一个原根，且$gcd(a,n)=1,a∈Z$，则存在唯一整数$x$使得$g^x \equiv a \pmod n$成立，我们称$x$为$g$为底模$n$的一个指标，记为$x=ind_g(a)$
一般求解上述方程，求出的是解的个数和解的和，这一类问题已经超出我们讨论的范围，对于这一类方程就拓展到这里，读者可以自行查阅相关资料深入探究。
------------
$ \ \ \ \ $ **②形如$a^x \equiv b \pmod m$的一类方程**
问题：
$ \ \ \ \ $ 给定整数$a,b,p$,（$p$相当于原方程的$m$），$gcd(a,p)=1$，求非负整数$x$，使得原方程成立。
- **$BSGS$算法**
1. 设 $x=i*t-j, \ t=$⌈$\sqrt p$⌉，$0≤j≤t-1$，则原方程化为$a^{i*t-j }\equiv b \pmod p$，即$a^{t*i} \equiv b*a^j \pmod p$。
1. 对于所有$j∈[0,t-1]$，把$b*a^j\mod p$插入一个$Hash$表。
1. 枚举所有$i$可能的取值，（$i∈[0,t]$），求出$a^{t*i}\mod p$，在$Hash$表中查找是否存在对应的$j$，更新答案即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
int power(int a, int x, int p) {
int ans = 1;
while(x) {
if(x & 1) ans = ans * a % p;
x >>= 1, a = a * a % p;
}
return ans;
}
int BGBS(int a, int b, int p) {
map<int, int> hash; hash.clear();
b %= p;
int t = (int)sqrt(p) + 1;
for(int j = 0; j < t; j++) {
int val = (long long) b * power(a, j, p);
hash[val] = j;
}
a = power(a, t, p);
if(a == 0) return b == 0 ? 1 : -1;
for(int i = 0; i <= t; i++) {
int val = power(a, i, p);
int j = hash.find(val) == hash.end() ? -1 : hash[val];
if(j >= 0 && i * t - j >= 0) return i * t - j;
}
return -1;
}
int main() {
int a, b, p;
scanf("%d %d %d", &a, &b, &p);
printf("%d",BGBS(a, b, p));
return 0;
}
```
上述算法的时间复杂度为 $ \sqrt p $。
※章末练习
------------
- $Part1$：**模板题**
1. [P1495 曹冲养猪](https://www.luogu.org/problemnew/show/P1495)（中国剩余定理）
1. [P3811 【模板】乘法逆元](https://www.luogu.org/problemnew/show/P3811)（乘法逆元）
1. [P1082 同余方程](https://www.luogu.org/problemnew/show/P1082)（扩展欧几里得算法）
1. [P3868 [TJOI2009]猜数字](https://www.luogu.org/problemnew/show/P3868)（中国剩余定理）
1. [P5431 【模板】乘法逆元2](https://www.luogu.org/problemnew/show/P5431)（乘法逆元）
1. [P4777 【模板】扩展中国剩余定理（EXCRT）](https://www.luogu.org/problemnew/show/P4777)（扩展中国剩余定理）
- $Part2$：**练习题**(带*号为选做题目)
7. [P2054 [AHOI2005]洗牌](https://www.luogu.org/problemnew/show/P2054)
1. [P1516 青蛙的约会](https://www.luogu.org/problemnew/show/P1516)
1. [P2155 [SDOI2008]沙拉公主的困惑](https://www.luogu.org/problemnew/show/P2155)
1. [P4861 按钮](https://www.luogu.org/problemnew/show/P4861)
1. [P4195 【模板】exBSGS/Spoj3105 Mod](https://www.luogu.org/problemnew/show/P4195)
1. [P2480 [SDOI2010]古代猪文](https://www.luogu.org/problemnew/show/P2480)
1. [P2485 [SDOI2011]计算器](https://www.luogu.org/problemnew/show/P2485)
1. [P3846 [TJOI2007]可爱的质数](https://www.luogu.org/problemnew/show/P3846)
1. **\***[P3301 [SDOI2013]方程](https://www.luogu.org/problemnew/show/P3301)
1. [P4884 多少个1？](https://www.luogu.org/problemnew/show/P4884)
1. [P3306 [SDOI2013]随机数生成器](https://www.luogu.org/problemnew/show/P3306)
1. [P4774 [NOI2018]屠龙勇士](https://www.luogu.org/problemnew/show/P4774)
1. [P1446 [HNOI2008]Cards](https://www.luogu.org/problemnew/show/P1446)
1. [P3726 [AH2017/HNOI2017]抛硬币](https://www.luogu.org/problemnew/show/P3726)
1. [P2020 [NOI2011]兔农](https://www.luogu.org/problemnew/show/P2020)
**注**：以上题目中第13题 **P2485计算器** 为[质数筛法详解](https://www.luogu.org/blog/Ning-H/primes)一章中选做题目
学习完本章后，[质数筛法详解](https://www.luogu.org/blog/Ning-H/primes)中的部分选做题目也可以完成。
$END$
------------
$PS:$
1. **部分材料参考于李煜东《算法竞赛进阶指南》。**
1. **部分材料来源于百度百科。**
1. **中国剩余定理部分资料参考[ 中国剩余定理 && 扩展中国剩余定理](https://blog.csdn.net/niiick/article/details/80229217)**