同余

· · 算法·理论

同余

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

同余概念

同余的定义

同余:设 m正整数,若 ab整数,且 m|(a-b),则称 abm 同余。也就是说,a 除以 m 的余数和 b 除以 m 余数相同;或者说,a-b 除以 m 的余数为 0

abm 同余记为:

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}^51 \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;
}

习题