同余
charlieqi
·
·
算法·理论
同余
同余是数论的一个基本理论,是很巧妙的工具,它使人们能够用等式的形式简洁地描述整除关系。
同余概念
同余的定义
同余:设 m 是正整数,若 a 和 b 是整数,且 m|(a-b),则称 a 和 b 模 m 同余。也就是说,a 除以 m 的余数和 b 除以 m 余数相同;或者说,a-b 除以 m 的余数为 0。
把 a 和 b 模 m 同余记为:
1. $$
\because 7|(18-4)
\\
\therefore 18 \equiv 4\pmod7
$$
2. $$
3\equiv -6\pmod 9
$$
剩余系:一个模 $m$ 完全剩余系是一个**整数的集合**,使每个整数**恰**与此集合中的一个元素模 $m$ **同余**。如,整数 $0,1,...,m-1$ 的集合是模 $m$ 的完全剩余系,称为**模 $m$ 最小非负剩余的集合**。
### 定理和性质
若 $a$ 和 $b$ 是**整数**,$m$ 为**正整数**,则 $a\equiv b\pmod m$ 当且仅当 $a\bmod m=b\bmod m$。
**把同余式转换为等式**。若 $a$ 和 $b$ 是**整数**,则 $a\equiv b\pmod m$ 当且仅当存在一整数 $k$,使 $a=b+km$ 成立。例如 $19\equiv -2\pmod 7$,因为 $19=-2+3\times 7$。
设 $m$ 是**正整数**,模 $m$ 同余满足:
1. 自反性:若 $a$ 是**整数**,则 $a\equiv a\pmod m$。
2. 对称性:若 $a$ 和 $b$ 是**整数**,且 $a\equiv b\pmod m$,则 $b\equiv a\pmod m$。
3. 传递性:若 $a,b,c$ 是**整数**,且 $a\equiv b\pmod m$ 和 $b\equiv c\pmod m$,则 $a\equiv c\pmod m$。
关于同余的加减乘除,若 $a,b,c,m$ 均为**整数**,且 $m>0$,$a\equiv b\pmod m$,$c\equiv d\pmod m$,则有以下性质:
| 运算 | 简单表达 | 一般表达 |
| :---: | :--------------------: | :--------------------: |
| 1. 加 | $a+c\equiv b+c\pmod m$ | $a+c\equiv b+d\pmod m$ |
| 2. 减 | $a-c\equiv b-c\pmod m$ | $a-c\equiv b-d\pmod m$ |
| 3. 乘 | $ac\equiv bc\pmod m$ | $ac\equiv bd\pmod m$ |
4. 除。在同余式两边同时除以一个**整数**,结果**不一定同余**。
5. 幂。若 $a,b,k,m$ 是**整数**,且 $k,m>0$,$a\equiv b\pmod m$,则 $a^k\equiv b^k\pmod m$。
## 一元线性同余方程
设 $x$ 是**未知数**,给定 $a,b,m$,求**整数** $x$,满足 $ax\equiv b\pmod m$。
$ax\equiv b\pmod m$ 表示 $ax-b$ 是 $m$ 倍数,设为 $-y$ 倍,则有 $ax+my=b$,这就是**二元线性丢番图方程**。因此,求解一元线性同余方程**等价于**求解二元线性丢番图方程。
方程是否有解?几个解?如何求解?和二元线性丢番图方程一样,线性同余方程也有类似的定理。
定理1:
设 $a,b,m$ 是**整数**,$m>0,\gcd(a,m)=d$。若 $d$ 不能整除 $b$,则 $ax\equiv b\pmod m$ **无解**;反之,有 $d$ 个模 $m$ 不同余的解。
推论1:
当 $a$ 和 $m$ 互质(互素)时,因为 $d=\gcd(a,m)=1$,所以方程只有**一个解**。
回到 $ax\equiv b\pmod m$,求解步骤为:
1. 求逆
2. 利用逆求出 $x$。
## 逆
求解一般形式的同余方程 $ax\equiv b\pmod m$,需使用**逆**(Inverse)。
### 逆的概念
给定**整数** $a$,且满足 $\gcd(a,m)=1$,称 $ax\equiv 1\pmod m$ 的一个解为 $a$ 模 $m$ 的逆,记作 $a^{-1}$。
例如,$7x\equiv 1\pmod {27}$,有一个解是 $x=4$,$4$ 是 $7$ 模 $21$ 的逆。所有解**都是** $7$ 模 $21$ 的逆。
我们可以借助丢番图方程理解逆的概念,$7x\equiv 1\pmod {27}$ 即为方程 $7x+27y=1$,$x=4$ 是 $7$ 模 $21$ 的逆,$4\times 7-1$ 能**整除** $31$。
<font color=red> 注意:</font>在做题时,模 $m$ **最好**是一个**大于** $a$ 的**素数**,才可以保证 $\gcd(a,m)=1$。
### 求逆
有多种方法可以求逆,在不同情况要选用合适的算法。
1. 扩展欧几里得算法求**单个**逆
[洛谷P1082 [NOIP2012 提高组] 同余方程](https://www.luogu.com.cn/problem/P1082)即求解同余方程 $ax\equiv b\pmod m$。
> # [NOIP2012 提高组] 同余方程
>
> ## 题目描述
>
> 求关于 $ x$ 的同余方程 $ a x \equiv 1 \pmod {b}$ 的最小正整数解。
>
> ## 输入格式
>
> 一行,包含两个整数 $a,b$,用一个空格隔开。
>
> ## 输出格式
>
> 一个整数 $x_0$,即最小正整数解。输入数据保证一定有解。
>
> ## 样例 #1
>
> ### 样例输入 #1
>
> ```
> 3 10
> ```
>
> ### 样例输出 #1
>
> ```
> 7
> ```
>
> ## 提示
>
> ### 数据规模与约定
>
> - 对于 $40\%$ 的数据,$2 ≤b≤ 1,000$;
> - 对于 $60\%$ 的数据,$2 ≤b≤ 50,000,000$;
> - 对于 $100\%$ 的数据,$2 ≤a, b≤ 2,000,000,000$。
先用扩展欧几里得算法求出 $ax+my=1$ 的一个特解 $x_0$,通解是 $x=x_0+mn$。然后通过取模操作计算最小整数解 $((x_0\bmod m)+m)\bmod m$,因为 $m>0$,可以**保证**结果是**整数**。
```cpp
long long mod_inverse(long long a,long long m){
long long x,y;
exgcd(a,m,x,y);
return (x%m+m)%m;//保证返回最小整数解。
}
int main(){
long long a,m;
cin>>a>>m;
cout<<mod_inverse(a,m);
return 0;
}
```
2. 费马小定理求**单个**逆
设 $n$ 是**素数**,$a$ 是**正整数**且与 $n$ 互素(互质),有 $a^{n-1}\equiv 1\pmod n$。
$a\cdot a^{n-2}\equiv 1\pmod n$,那么 $a^{n-2}\bmod n$ 就是 $a$ 模 $n$ 的逆。计算需使用**快速幂取模函数(手写)**。
```cpp
long long mod_inverse(long long a,long long mod){
return fast_pow(a,mod-2,mod);
}
```
3. 递推求**多个**逆
如果要求 $1\sim n$ 内的**所有**逆,可以使用**递推法**。时间复杂度为 $O(n)$。
> [洛谷P3811 【模板】模意义下的乘法逆元](https://www.luogu.com.cn/problem/P3811)
>
> # 【模板】模意义下的乘法逆元
>
> ## 题目背景
>
> 这是一道模板题
>
> ## 题目描述
>
> 给定 $n,p$ 求 $1\sim n$ 中所有整数在模 $p$ 意义下的乘法逆元。
>
> 这里 $a$ 模 $p$ 的乘法逆元定义为 $ax\equiv1\pmod p$ 的解。
>
> ## 输入格式
>
> 一行两个正整数 $n,p$。
>
> ## 输出格式
>
> 输出 $n$ 行,第 $i$ 行表示 $i$ 在模 $p$ 下的乘法逆元。
>
> ## 样例 #1
>
> ### 样例输入 #1
>
> ```
> 10 13
> ```
>
> ### 样例输出 #1
>
> ```
> 1
> 7
> 9
> 10
> 8
> 11
> 2
> 5
> 3
> 4
> ```
>
> ## 提示
>
> $ 1 \leq n \leq 3 \times 10 ^ 6$,$n < p < 20000528 $。
>
> 输入**保证** $ p $ 为**质数**。
首先,$i=1$ 的逆是 $1$。求 $i>1$ 时的逆,用递推法。
1. 设 $p/i=k$,余数是 $r$,即 $k\cdot i+r\equiv 0\pmod p$。
2. 在等式**两边同时**乘 $i^{-1}\cdot r^{-1}$,得到 $k\cdot r^{-1}+i^{-1}\equiv 0\pmod p$。
3. 移项得 $i^{-1}\equiv -k\cdot r^{-1}\pmod p$。
```cpp
inv[1]=1;
for(int i=2;i<=n;i++){
inv[i]=1ll*(p-p/i)*inv[p%i]%p;
}
```
### 用逆求解同余方程
逆有什么用处?如果有 $a$ 模 $m$ 得一个逆,可以用来求解形如 $ax\equiv b\pmod m$ 的任何同余方程。
记 $a^{-1}$ 是 $a$ 的一个逆,有 $a^{-1}a\equiv 1\pmod m$。在 $ax\equiv b\mod m$ 的两边同时乘以 $a^{-1}$,得到 $a^{-1}ax\equiv a^{-1}b\pmod m$,即 $x\equiv a^{-1}b\pmod m$。
例如,为了求出 $8x\equiv 22\pmod {31}$ 的解,可以在两边同时乘以 $4$,$4$ 是 $8$ 模 $31$ 的一个逆,得 $4\times 8x\equiv 4\times 22\pmod {31}$,因此 $x\equiv 88\pmod {31}\equiv 26\pmod {31}$。
定理2:
设 $p$ 是**素数**,正整数 $a$ 是其自身模 $p$ 的逆,当且仅当 $a\equiv 1\pmod p$ 或 $a\equiv -1\pmod p$。
证明
若 $a\equiv 1\pmod p$ 或 $a\equiv -1\pmod p$,有 $a^2\equiv 1\pmod p$,所以 $a$ 是其自身模 $p$ 的逆。反过来**也成立**。
### 逆与除法取模
逆的一个重要应用就是**求除法的模**。求 $(a/b)\bmod m$,即 $a$ 除以 $b$,然后对 $m$ 取模。这里的 $a$ 和 $b$ 是很大的数,如 $a=n!$,容易溢出,导致取模出错。用逆可以**避免**除法计算,设 $b$ 的逆元是 $b^{-1}$,有
$$
(a/b)\bmod m=((a/b)\bmod m)((bb^{-1})\bmod m)=(a/b\times bb^{-1})\bmod m=(ab^{-1})\bmod m
$$
经过如上推导,除法运算转换为乘法运算,即
$$
(a/b)\bmod m=(ab^{-1})\bmod m=(a\bmod m)(b^{-1}\bmod m)\bmod m
$$
## 同余方程组
我们知道,同余方程 $ax\equiv b(\bmod m)$ 有解当且仅当 $\gcd(a,m)$ 能整除 $b$,可以解得 $x\equiv a^{'}(\bmod m^{'})$,所以这也是同余方程的**一般形式**。而同余方程**组**,即
$$
x\equiv a_1\pmod {m_1}\\
x\equiv a_2\pmod {m_2}\\
.\\
.\\
.\\
x\equiv a_n\pmod {m_n}\\
$$
解决这个问题有两种方法:**中国剩余定理**和**迭代法**。前者适用于 $m_1,m_2,...,m_n$ **两两互素**的情况,且**一定有解**。后者是**更一般条件**的**通用解法**,但可能无解。
### 中国剩余定理
设 $m_1,m_2,...,m_n$ 是**两两互素**的**正整数**,则同余方程组 $x\equiv a_1\pmod {m_1},
x\equiv a_2\pmod {m_2},
.
.
.
x\equiv a_n\pmod {m_n}$ 有**整数**解,且模 $M=m_1m_2...m_n$ **唯一**,解为
$$
x\equiv (a_1M_1M_1^{-1}+a_2M_2M_2^{-1}+...+a_nM_nM_n^{-1})(\bmod M)
$$
其中,$M_i=M/m_i$,$M_i^{-1}$ 为 $M_i$ 模 $m_i$ 的逆元。
代码写起来十分容易,将求逆元的方法和解方程相结合即可,推荐使用递推法求逆元,这里给出扩展欧几里得算法求逆元。
代码:
```cpp
#include<bits/stdc++.h>
typedef long long ll;
const int maxn=1e5+10;
using namespace std;
int n;
int a[maxn],m[maxn],M[maxn],M_[maxn];
ll fac=1;
ll exgcd(ll a,ll b,ll&x,ll&y){
if(!b){
x=1;
y=0;
return a;
}
ll d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
ll mod_inverse(ll a,ll mod){
ll x,y;
exgcd(a,mod,x,y);
return (x%mod+mod)%mod;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>m[i];
fac*=m[i];
}
for(int i=1;i<=n;i++){
M[i]=fac/m[i];
M_[i]=mod_inverse(M[i],m[i]);
}
ll ans=0;
for(int i=1;i<=n;i++){
ans+=a[i]*M[i]*M_[i];
}
cout<<ans%fac;
return 0;
}
```
### 迭代法
中国剩余定理固然简单,但是有**限制条件**。为了解决这个问题,要使用**迭代法**。
迭代法的思路很简单,每次合并两个同余式,逐步合并,直到**合并完所有等式**,只剩下一个,就得到了答案。
合并时,把同余方程转换为等式更容易操作。这是利用了同余的一个性质:若 $x$ 和 $a$ 是**整数**,则 $x\equiv a(\bmod m)$ 当且仅当存在整数,使 $x=a+km$ 成立。
1. 举例
解方程:
$$
x\equiv 2\pmod 3\\
x\equiv 3\pmod 5\\
x\equiv 2\pmod 7
$$
1. 把第一个式子 $x\equiv 2\pmod 3$ 转换为 $x=2+3t$,代入第二个同余式,的 $2+3t\equiv 3\pmod 5$。
2. 求解 $2+3t\equiv 3\pmod 5$。
$$
2+3t\equiv 3\pmod 5=3t\equiv (3-2)\pmod 5=3t\equiv 1\pmod 5\\
\because \gcd(3,5)|1\\
\therefore \text{有解}
$$
然后求解 $3t\equiv 1\pmod 5$,先求除 $3$ 模 $5$ 的逆,为 $2$,所以解得 $t\equiv 2\pmod 5$,转换为 $t=2+5u$。
3. 把 $t=2+5u$ 代入 $x=2+3t$ 得 $x=8+15u$,即 $x\equiv 8\pmod {15}$。
4. 把 $x=8+15u$ 代入第三个同余式,得 $8+15u\equiv 2\pmod 7$。
5. 求解 $8+15u\equiv 2\pmod 7
$$
8+15u\equiv 2\pmod 7=15u\equiv -6\pmod 7
\\\because \gcd(15,7)|-6
\\\therefore \text{有解}
$$
然后求解 $15u\equiv -6\pmod 7$,先求除 $15$ 模 $7$ 的逆,为 $1$,所以解得 $u\equiv 1\pmod 7$,转换为 $u=1+7v$。
- 把 u=1+7v 代入 x=8+15u,得 x=23+105v,即 x\equiv 23\pmod {105}。
-
编程步骤
步骤 |
例子 |
合并两个式子:x=a_1+Xm_1\\ x=a_2+Ym_2 |
x=2+3X\\ x=3+5Y |
两个等式相等:a_1+Xm_1=a_2+Ym_2,移项得 Xm_1+(-Y)m_2=a_2-a_1 |
2+3X=3+5Y\\ 3X+5(-Y)=1 |
解形如 aX+bY=c 得丢番图方程,先求出 X_0。 |
X_0=2 |
通解是 X=X_0c/d+(b/d)n,最小值 t=(X_0c/d)\bmod(b/d)。 |
t=2 |
把 X=t 代入 x=a_1+Xm_1 求出原等式的一个特解 x^{'}。 |
x^{'}=2+2\times 3=8 |
合并后新的 x=a+Xm,m=m_1m_2/\gcd(m_1,m_2),a=x^{'}。 |
m=3\times 5/1=15,a=8,合并后方程即为 x\equiv 8\pmod {15}。 |
P4777 【模板】扩展中国剩余定理(EXCRT)
【模板】扩展中国剩余定理(EXCRT)
题目描述
给定 n 组非负整数 a_i, b_i ,求解关于 x 的方程组的最小非负整数解。
\begin{cases}x\equiv b_1\pmod{a_1}\\x\equiv b_2\pmod{a_2}\\\dots\\x\equiv b_n\pmod{a_n}\end{cases}
输入格式
输入第一行包含整数 n。
接下来 n 行,每行两个非负整数 a_i, b_i。
输出格式
输出一行,为满足条件的最小非负整数 x。
样例 #1
样例输入 #1
3
11 6
25 9
33 17
样例输出 #1
809
提示
对于 100 \% 的数据,1 \le n \le {10}^5,1 \le b_i,a_i \le {10}^{12},保证所有 a_i 的最小公倍数不超过 {10}^{18}。
请注意程序运行过程中进行乘法运算时结果可能有溢出的风险。
数据保证有解。
#include<bits/stdc++.h>
typedef long long ll;
const int maxn=100010;
using namespace std;
int n;
ll a[maxn],m[maxn];
ll fast_pow(ll a,ll b,ll mod){
ll res=0;
while(b){
if(b&1){
res=(res+a)%mod;
}
a=(a+a)%mod;
b>>=1;
}
return res;
}
ll exgcd(ll a,ll b,ll&x,ll&y){
if(!b){
x=1;
y=0;
return a;
}
ll d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
ll excrt(){
ll x,y,m1=m[1],a1=a[1],ans=0;
for(int i=2;i<=n;i++){
ll a2=a[i],m2=m[i];
ll a=m1,b=m2,c=(a2-a1%m2+m2)%m2;
ll d=exgcd(a,b,x,y);//特解。
if(c%d){//无解。
return -1;
}
x=fast_pow(x,c/d,b/d);//最小值。
ans=a1+x*m1;//特解。
m1=m2/d*m1;//新m1。
ans=(ans%m1+m1)%m1;//最小正整数解。
a1=ans;//新a1。
}
return ans;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>m[i]>>a[i];
}
cout<<excrt();
return 0;
}
习题
- 洛谷P4549 【模板】裴蜀定理
- 洛谷P2613 【模板】有理数取余
- 洛谷P3811 【模板】模意义下的乘法逆元
- 洛谷P5431 【模板】模意义下的乘法逆元 2
- 洛谷P1082 [NOIP2012 提高组] 同余方程
- 洛谷P3951 [NOIP2017 提高组] 小凯的疑惑 / [蓝桥杯 2013 省] 买不到的数目
- 洛谷P4777 【模板】扩展中国剩余定理(EXCRT)
- 洛谷P3868 [TJOI2009] 猜数字
- 洛谷P4774 [NOI2018] 屠龙勇士
- 洛谷P5345 【XR-1】快乐肥宅
- 洛谷UVA10551 Basic Remains
- 洛谷SP7035 CRYPTON - The Embarrassed Cryptographer
- 洛谷UVA11105 H-半素数 Semi-prime H-numbers
- 洛谷UVA756 Biorhythms