算法竞赛专题解析（22）：数论--同余

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法竞赛专题解析（22）：数论--同余，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含12177字，纯文字阅读大概需要18分钟。

内容图文

本系列文章将于2021年整理出版。前驱教材：《算法竞赛入门到进阶》 清华大学出版社
网购：京东 当当 ??作者签名书：点我
公众号同步：算法专辑 ??
暑假福利：胡说三国
有建议请加QQ 群：567554289

目录

• 1. 同余概述
  • 1.1. 同余定义
  • 1.2. 一些定理和性质
• 2. 一元线性同余方程
• 3. 逆
  • 3.1.逆的概念
  • 3.2.求逆
  • 3.3. 用逆求解同余方程
• 4. 同余方程组
  • 4.1. 中国剩余定理
  • 4.2. 迭代法

?? 同余是很巧妙的工具，它使得人们能够用等式的形式来简洁地描述整除关系。
?? 在阅读本节内容时，请对照上一节“线性丢番图方程”的内容，有很多类似的地方。

1. 同余概述

1.1. 同余定义

??设m是正整数，若a和b是整数，且\(m | (a - b)\)，则称\(a\)和\(b\)模\(m\)同余。也就是说，\(a\)除以\(m\)得到的余数，和\(b\)除以\(m\)的余数相同；或者说，\(a - b\)除以\(m\)，余数是0。
??把\(a\)和\(b\)模\(m\)同余记为 \(a\equiv b (mod m)\)，\(m\)称为同余的模。例子：
??（1）因为7|(18-4)，所以18\(\equiv\) 4 (mod 7)，18除以7余数是4，4除以7的余数也是4；
??（2）3\(\equiv\) 6 (mod 9)，3除以9余数是3，-6除以9的余数也是3；
??（3）13和5模9不同余，因为13除以9余数是4，5除以9余数是5。

1.2. 一些定理和性质

??（1）若\(a\)和\(b\)是整数，\(m\)为正整数，则\(a\equiv b (mod\ m)\)当且仅当\(a\ mod\ m = b mod\ m\)。
??（2）把同余式转换为等式。若\(a\)和\(b\)是整数，则\(a\equiv b (mod\ m)\)当且仅当存在整数，使得\(a = b + km\)。例如：19-2 (mod 7)，有19 = -2 + 3 ? 7。
??（3）设\(m\)是正整数，模\(m\)的同余满足下面的性质：
??1）自反性。若\(a\)是整数，则\(a\equiv a (mod\ m)\)
??2）对称性。若\(a\)和\(b\)是整数，且\(a\equiv b (mod\ m)\)，则\(b\equiv a (mod\ m)\)。
??3）传递性。若\(a、b、c\)是整数，且\(a\equiv b (mod\ m)和b\equiv c (mod m)\)，则\(ac (mod\ m)\)。

2. 一元线性同余方程

??一元线性同余方程：设\(x\)是未知数，给定\(a、b、m\)，求整数\(x\)，满足 \(ax\equiv b (mod\ m)\)。
??研究线性同余方程有什么用处？\(ax\equiv b(mod\ m)\)表示\(ax - b\)是\(m\)的倍数，设为 \(-y\)倍，则有\(ax + my = b\)，这就是二元线性丢番图方程。所以，求解一元线性同余方程等同于求解二元线性丢番图方程。
??方程是否有解？如果有解，有多少解？如何求出解？与线性丢番图的定理一样，线性同余方程也有类似的定理。
??定理：设\(a，b\)和\(m\)是整数，\(m > 0，gcd(a, m) = d\)，若\(d\)不能整除b，则\(ax\equiv b (mod\ m)\)无解，若\(d\)能整除\(b\)，则\(ax\equiv b (mod\ m)\)有\(d\)个模\(m\)不同余的解。
??定理的前半部分可以概况为：\(ax\equiv b (mod\ m)\)有解的充分必要条件是\(gcd(a, m)\)能整除b。
??定理的后半部分说明了解的情况。与线性丢番图方程类似，如果有一个特解是 \(x_0\) ，那么通解是\(x = x_0 + (m/d)n\)，当\(n = 0, 1, 2, ..., d -1\)时，有\(d\)个模\(m\)不同余的解。
??推论：\(a\)和\(m\)互素时，因为\(d = gcd(a, m)=1\)，所以线性同余方程\(ax\equiv b (mod\ m)\)有唯一的模\(m\)不同余的解。这个推论在下一节的逆中有应用。
??最后回到求解\(ax\equiv b (mod\ m)\)的问题：首先求逆，然后利用逆求得\(x\)。

3. 逆

??求解一般形式的同余方程\(ax\equiv b (mod\ m)\)，需要用到逆。

3.1.逆的概念

??给定整数a，且满足\(gcd(a, m) = 1\)，称 \(ax\equiv 1(mod\ m)\)的一个解为\(a\)模\(m\)的逆。记为\(a^{-1}\)。
??例如：\(8x\equiv 1(mod\ 31)\)，有一个解是\(x\) = 4，4是8模31的逆。所有的解，例如35、66等，都是8模31的逆。
??可以借助丢番图方程理解逆的概念，\(8x\equiv 1(mod\ 31)\)即方程\(8x + 31y = 1\)，\(x\) = 4是8模31的逆，4×8-1能整除31。

3.2.求逆

??有多种方法可以求逆。
（1）扩展欧几里得求单个逆
??下面的例题是求逆，即求解同余方程\(ax\equiv 1(mod\ m)\)。

---

同余方程（求逆） 洛谷 P1082
题目描述：求关于x的同余方程\(ax\equiv 1(mod\ m)\)的最小正整数解。2≤a, m≤2,000,000,000。

---

??题解：\(ax\equiv 1(mod\ m)\)，即丢番图方程\(ax + my = 1\)，先用扩展欧几里得求出\(ax + my = 1\)的一个特解\(x_0\)，通解是\(x = x_0 + mn\)。然后通过取模操作算最小整数解\(( (x_0 mod\ m) + m) mod\ m\)，因为\(m\) > 0，可以保证结果是正整数。

long long mod_inverse(long long a, long long m){    //求逆
	long long x,y;
    extend_gcd(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(mod\ n)\)。
??\(a a^{n-2}\equiv 1(mod\ n)\)，那么\(a^{n-2} mod\ n\)就是\(a\)模\(n\)的逆。计算需要用到快速幂取模fast_pow()，参考前面章节“大素数的判定”。快速幂取模的复杂度是\(O(log n)\)的。

long long mod_inverse(long long a,long long mod){
   return fast_pow(a,mod - 2,mod);           
}

（3）递推求多个逆
??如果要求1 ~ n内所有的逆，可以用递推。复杂度是O(n)的。

---

乘法逆元 洛谷 P3811
题目描述：给定 \(n，p\)，求 \(1 ~ n\) 中所有整数在模 \(p\) 意义下的乘法逆元。
\(1≤n≤3×10^6\)，\(n < p < 20000528\)，\(p\)为质数。
输入：一行两个正整数\(n、p\)。
输出：输出\(n\)行，第\(i\)行表示\(i\)在模\(p\)下的乘法逆元。

---

??首先，\(i=1\)时逆是1。下面求\(i > 1\)时的逆，用递推法。
??设\(p/i = k\)，余数是\(r\)，即\(k i + r\equiv 0(mod\ p)\)；
??在两边乘\(i^{-1} r^{-1}\)，得到\(k r^{-1} + i^{-1}\equiv 0 (mod\ p)\)；
??移项得\(i^{-1}\equiv - k r^{-1} (mod\ p)\) ，即\(i^{-1}\equiv - p/i r^{-1} (mod\ p)\) ，\(i^{-1}\equiv (p - p/i) r^{-1} (mod\ p)\)。

long long inv[maxn];
void inverse(long long n, long long p){
    inv[1]=1;
    for(int i = 2;i<maxn;i++)
       inv[i]= (p - p/i) * inv[p%i] % p;
}

??下面给出一个求逆的例题。

---

A/B hdu 1576
题目描述：求(A/B)%9973，但由于A很大，我们只给出n (n = A%9973)(我们给定的A必能被B整除，且gcd(B, 9973) = 1)。
输入：第一行是T，表示有T组数据。每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
输出：对每组数据，输出(A/B)%9973。

---

题解：
??设答案\(k = (A/B) % 9973\)。
?? 做以下变换：\(A/B = k + 9973 x，A = kB + 9973 x B\)；
?? 把\(A % 9973 = n\)代入得\(k B % 9973 = n\)，即\(k B = n + 9973y\)；
?? 两边除\(n\)得\((k/n) B + (-y/n) 9973 = 1\)，这是形如\(ax + by = 1\)的丢番图方程，即\(ax\equiv 1(mod\ m)\)，其中\(x = k/n\)。求解逆\(x\)，得到\(k/n\)，再乘以\(n\)，就是\(k\)。

3.3. 用逆求解同余方程

??逆有什么用？如果有\(a\)模\(m\)的一个逆，可以用来解如\(ax\equiv b (mod\ m)\)的任何同余方程。
?? 记\(a^{-1}\)是\(a\)的一个逆，有\(a^{-1}a\equiv 1(mod\ m)\)。在\(ax\equiv b (mod\ m)\)的两边同时乘以\(a^{-1}\)，得到\(a^{-1}ax\equiv a^{-1}b(mod\ m)\)，即\(x\equiv a^{-1}b (mod\ m)\)。
?? 例如：为了求出\(8x\equiv 22 (mod\ 31)\)的解，可以两边乘以4，4是8模31的一个逆，得\(4 * 8x = 4 * 22 (mod\ 31)\)，因此\(x\equiv 88 (mod\ 31)\equiv 26 (mod\ 31)\)。
?? 定理：设\(p\)是素数，正整数\(a\)是其自身模\(p\)的逆，当且仅当\(a\equiv 1 (mod\ p)\)或\(a\equiv -1 (mod\ p)\)。
?? 证明：若\(a\equiv 1 (mod\ p)\)或\(a\equiv -1 (mod\ p)\)，有\(a^2\equiv 1 (mod\ p)\)，所以\(a\)是其自身模\(p\)的逆。反过来也成立。

4. 同余方程组

??根据上一节的讨论，同余方程\(ax\equiv b (mod\ m)\)有解时，即\(gcd(a, m)\) 能整除\(b\)时，可以解得\(x\equiv a' (mod\ m')\)，所以这也是同余方程的一般形式。本节讨论同余方程组的求解：
????\(x\equiv a_1 (mod\ m_1)\)
????\(x\equiv a_2 (mod\ m_2)\)
????...
????\(x\equiv a_r (mod\ m_r)\)
??例：有一个数\(x\)，被3除余2，被5除余3，被7除余2，列成同余方程就是：
????\(x\equiv 2 (mod\ 3)\)
????\(x\equiv 3 (mod\ 5)\)
????\(x\equiv 2 (mod\ 7)\)
??求解结果是：\(x = 23 + 3 × 5 ×7 × n\)，\(n ≥ 0\)，或者写为\(x\equiv 23 (mod\ 3 × 5 × 7)\)，\(x\)的最小正整数解是23。
??本节介绍中国剩余定理和迭代法，前者是用于\(m_1，m_2，...，m_r\)两两互素情况下的优秀解法，后者是更一般条件下的通用解法。适用中国剩余定理的方程组肯定有解，而迭代法处理的更一般情况，可能是无解的。

4.1. 中国剩余定理

??中国剩余定理^[1]：设\(m_1，m_2，...，m_r\)是两两互素的正整数，则同余方程组
????\(x\equiv a_1 (mod\ m_1)\)
????\(x\equiv a_2 (mod\ m_2)\)
????...
????\(x\equiv a_r (mod\ m_r)\)
??有整数解，并且模\(M = m_1m_2...m_r\)唯一，解为：
??\(x=(a_1M_1M_1^{-1} + a_2M_2M_2^{-1} + ... + a_rM_rM_r^{-1}) (mod\ M)\)
??其中\(M_i = M/m_i\)，\(M_i^{-1}\)为\(M_i\)模\(m_i\)的逆元。
?? 读者可以尝试自己证明。可以用数学归纳法，从\(i-1个\)方程推广到\(i\)个方程。

?? 例题：解同余方程组\(x\equiv 2 (mod\ 3)，x\equiv 3 (mod\ 5)，x\equiv 2 (mod\ 7)\)。
?? 解题步骤：
?? （1）\(M = 3 ×5 ×7 = 105，M1 = 105/3 = 35，M2 = 105/5 = 21，M3 = 105/7 = 15\)。
?? （2）求逆：\(M_1^{-1} = 2，M_2^{-1} = 1，M_3^{-1} = 1\)。
?? （3）最后计算\(x：x\equiv 2×35×2 + 3×21×1 + 2×15×1\equiv 233\equiv 23(mod 105)\)。

4.2. 迭代法

??中国剩余定理的编码很容易，但是它的限制条件是方程组的\(m_1，m_2，...，m_r\)两两互素。如果不互素，该如何解题呢？这就是迭代法。
??迭代法的思路很简单，就是每次合并两个同余式，逐步合并，直到合并完所有等式，只剩下一个，就得到了答案。
??合并的时候，把同余方程转化为等式更容易操作。这是根据同余的一个性质：若\(x\)和\(a\)是整数，则\(x\equiv a (mod\ m)\)当且仅当存在整数，使得\(x = a + km\)。

1、 示例
??以方程组\(x\equiv 2 (mod\ 3)，x\equiv 3 (mod\ 5)，x\equiv 2 (mod\ 7)\)为例，说明合并过程。下面的计算步骤，前3步合并了第1和第2个同余式，后面3步继续合并第3个同余式。
?? 1）把第1个同余式\(x\equiv 2 (mod\ 3)\)转换为\(x = 2 + 3t\)，代入第2个同余式得\(2 + 3t\equiv 3 (mod\ 5)\)。
?? 2）求解\(2 + 3t\equiv 3 (mod\ 5)\)。
?? 首先变为\(3t \equiv (3 - 2) (mod\ 5)\)，即\(3t \equiv 1 (mod\ 5)\)，因为\(gcd(3, 5)\)能整除1，所以有解。
?? 然后求解\(3t \equiv 1 (mod\ 5)\)：先求3模5的逆，是2，所以解得\(t\equiv 2(mod\ 5)\)，转换为等式\(t = 2 + 5u\)。
?? 3）第1个和第2个同余式合并的结果。把\(t = 2 + 5u\)代入\(x = 2 + 3t\)得\(x = 8 + 15u\)，即\(x\equiv 8 (mod\ 15)\)。
?? 4）把\(x = 8 + 15u\)代入第3个同余式得：\(8 + 15u \equiv 2 (mod\ 7)\)。
?? 5）求解\(8 + 15u\equiv 2 (mod\ 7)\)。
?? 首先变为\(15u\equiv -6 (mod\ 7)\)，\(gcd(15, 7)\)能整除\(-6\)，有解。
?? 然后求\(15u\equiv -6 (mod\ 7)\)：先求15模7的逆，是1，解得\(u\equiv 1(mod\ 7)\)，转换为\(u = 1 + 7v\)。
?? 6）得到合并结果。把\(u = 1 + 7v\)代入\(x = 8 + 15u\)，得\(x = 23 + 105v\)，即\(x\equiv 23(mod\ 105)\)。结束。

2、 编码步骤
??下面改用丢番图方程的形式，总结合并两个同余式的编码方法，并以合并上面的前2个等式为例。

步骤	例子
合并两个等式： \(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 = X_0 c / d + (b/d)n\) 最小值是\(t = (X_0 c / d) mod\ (b/d)\)	\(t = (X_0 c / d) mod\ (b/d)\) \(= (2×1/1) mod\ (5/1) = 2\)
把\(X = t\)代入\(x = a_1 + Xm_1\) 求得原等式的一个特解\(x'\)	得\(x' = 2 + 2×3 = 8\)
合并后的新\(x = a + Xm\)： \(m = m_1m_2/gcd(m_1, m_2)\) \(a = x'\)	\(m = 3×5/1 = 15\) \(a = 8\) 合并后的新方程是\(x = 8 + 15X\) 即\(x\equiv 8 (mod 15)\)

3、 例程
??下面用一个模板题给出线性同余方程组的代码。

---

扩展中国剩余定理 洛谷P4777
题目描述：给定n组非负整数\(a_i，m_i\)，求解关于\(x\)的方程组的最小非负整数解。1≤n≤10^5，1 ≤ ai ≤ 10^12，\(1 ≤ m_i < a_i\)，保证所有\(a_i\)的最小公倍数不超过 10^18。
????\(x\equiv a_1 (mod\ m_1)\)
????\(x\equiv a_2 (mod\ m_2)\)
????...
????\(x\equiv a_n (mod\ m_n)\)
输入：第一行是整数n，后面n行，每行两个非负整数\(a_i，m_i\)。
输出：输出一行，为满足条件的非负整数x。

---

??下面给出的代码^[2]，和前面“编码步骤”基本一致。
??注意代码中的细节，例如求\(t = (X_0 c / d) mod\ (b/d)\)的代码是\(mul(x, c/d, b/d)\)，目的是避免越界。其他细节见注释。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
int n;
ll ai[maxn], mi[maxn];
ll mul(ll a,ll b,ll mod){   //乘法取模：a*b % mod
    ll res=0;
    while(b>0){
        if(b&1) res=(res+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return res;
}
ll extend_gcd(ll a,ll b,ll &x,ll &y){   //扩展欧几里得
    if(b == 0){ x=1; y=0; return a;}
    ll d = extend_gcd(b,a%b,y,x);
    y -= a/b * x;
    return d;
}
ll excrt(){               //求解同余方程组，返回最小正整数解
    ll x,y;
    ll m1 = mi[1], a1 = ai[1];      //第1个等式
    ll ans = 0;
    for(int i=2;i<=n;i++){          //合并每2个等式       
        ll a2 = ai[i], m2 = mi[i];  // 第2个等式 
        //合并为：aX + bY = c      
        ll a = m1, b = m2, c = (a2 - a1%m2 + m2) % m2;
        //下面求解 aX + bY = c
        ll d = extend_gcd(a,b,x,y);  //用扩展欧几里得求x0
        if(c%d != 0) return -1;      //无解
        x = mul(x,c/d,b/d);          //aX + bY = c 的特解t，最小值         
        
        ans = a1 + x* m1;            //代回原第1个等式，求得特解x'
        m1 = m2/d*m1;                //先除再乘，避免越界。合并后的新m1
        ans = (ans%m1 + m1) % m1;    //最小正整数解
        a1 = ans;                    //合并后的新a1
    }
    return ans;
}

int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;++i)  
        scanf("%lld%lld",&mi[i],&ai[i]);
    printf("%lld",excrt());
    return 0;
}

---

1. 公元3世纪《孙子算经》中有一个问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰：二十三。”1247年，秦九韶在《数学九章》中给出了求解的一般方法“大衍求一术”，被称为“中国剩余定理（Chinese Remainder Theorem）”。秦九韶是全能型的天才，在多个领域有建树。 ??

2. 参考：https://www.luogu.com.cn/problem/solution/P4777 ??

内容总结

以上是互联网集市为您收集整理的算法竞赛专题解析（22）：数论--同余全部内容，希望文章能够帮你解决算法竞赛专题解析（22）：数论--同余所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---