同余

· · 算法·理论

同余

同余是数论的一个基本理论，是很巧妙的工具，它使人们能够用等式的形式简洁地描述整除关系。

同余概念

同余的定义

同余：设 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$。
  1. 把 u=1+7v 代入 x=8+15u，得 x=23+105v，即 x\equiv 23\pmod {105}。

  1. 编程步骤

    步骤 例子
    合并两个式子：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;
}

习题