同余方程题型整理

很多同余问题在题目包装下可能差异很大：周期相遇、循环运动、模意义下的方程、多个余数约束、指数未知量等，但在标准化处理后，往往都会变得类似。

一、线性同余方程

这一类问题最终都会化成 $ax\equiv b\pmod m$ 的形式，核心是判断它是否有解，并求出整个解类。

Q1

P1082 同余方程
求满足 $ax\equiv1\pmod b$ 的最小正整数 $x$。

数据规模：$2\le a,b\le 2\times10^9$。

同余式 $ax\equiv c\pmod m$ 等价于存在整数 $y$，使 $ax+my=c$。

根据裴蜀定理，方程有解当且仅当 $\gcd(a,m)\mid c$。令 $g=\gcd(a,m)$，若 $g\nmid c$ 则无解。

否则同时约去 $g$，得到 $\displaystyle \frac agx\equiv\frac cg\pmod{\frac mg}$，此时 $\displaystyle \gcd(\frac ag,\frac mg)=1$，可以利用逆元求出一个基础解。

因此线性同余实际上只有两步：先用 $gcd$ 判断可解性，再把方程约成系数与模数互质的形式。

笔记

对 $ax\equiv c\pmod m$，若 $g=\gcd(a,m)$ 且 $g\mid c$，那么模 $m$ 意义下共有 $g$ 个不同解。

若只关心整个解类，可以将其表示为模 $m/g$ 的一个剩余类。

Q2

P1516 青蛙的约会
两只青蛙位于一条首尾相接、总长为 $L$ 的纬度线上，初始坐标分别为 $x,y$。它们同时向同一方向跳，每次分别前进 $m,n$ 米，并且每次跳跃耗时相同。求它们最早经过多少次跳跃后落在同一点；若永远无法相遇，则输出 Impossible。

数据规模：$1\le x,y,m,n\le2\times10^9$，$x\ne y$，$1\le L\le2.1\times10^9$。

经过 $t$ 次跳跃以后，两只青蛙在展开后的坐标分别为 $x+mt$ 和 $y+nt$。由于纬度线首尾相接，实际位置只取决于它们模 $L$ 的余数。

因此两只青蛙相遇时满足 $x+mt\equiv y+nt\pmod L$，移项以后得到 $(m-n)t\equiv y-x\pmod L$，这就是一个线性同余方程。

注意到只有时间 $t$ 是未知数，所以把它看作 $x$，再整理式子，就可以得到这个线性同余方程了。

Q3

P2421 荒岛野人
有 $n$ 个野人在环形排列的 $M$ 个山洞中走。给定每个人的起点 $C_i$、速度 $P_i$ 和寿命 $L_i$。求最小的 $M$，使得任何两个野人在各自的寿命结束前，都不会在同一个洞穴相遇。

数据规模：$1\le n\le15$，$1\le C_i,P_i\le100$，$0\le L_i\le10^6$，并保证答案 $M\le10^6$。

在固定一个模数之后，每一对野人的相遇条件可以同上题一样转化为一个线性同余方程。

在固定一个 $M$ 之后，第 $i$ 个野人在第 $t$ 年的位置由 $C_i+P_i \cdot t$ 模 $M$ 决定。于是两个人 $i,j$ 在第 $t$ 年相遇时，需要满足 $(P_i-P_j) t\equiv C_j - C_i\pmod M$。

若方程无解，这一对野人不会相遇；若有解，则求出最小非负解 $t_0$。只有当 $t_0\le\min(L_i,L_j)$ 时，两人才会在有生之年发生冲突，否则这个解类不会影响当前 $M$ 的合法性。

所以对一个确定的 $M$，每一对野人的冲突都可以继续使用线性同余进行判定。不过这里要求的未知量 $M$ 出现在模数位置，随着 $M$ 改变，$\gcd(P_i-P_j,M)$ 和最小相遇时间都会变化，合法性并不单调。

因此不能从这些方程中直接构造出最小的 $M$。只需要注意合法山洞数至少为 $\max C_i$，于是从这个下界开始枚举 $M$，逐个检查所有野人对即可。

线性同余的识别

一般来说，当题目中出现“两个线性变化量在某个周期下相等”时，可以优先尝试移项得到 $ax\equiv b\pmod m$。

这一类题的主要难点通常在建模，求解本身基本统一为 gcd 判解、约分和 exgcd。

二、同余方程组

如果一个未知数同时满足多个周期条件，单个线性同余就不够了。此时通常先把每个条件化成 $x\equiv a_i\pmod{m_i}$ 的解类，再寻找这些解类的公共部分。

Q4

P1495 中国剩余定理 / 曹冲养猪
曹冲不知道猪场里究竟有多少头猪，只进行了若干次分圈实验。第 $i$ 次建造 $a_i$ 个猪圈后，恰好有 $b_i$ 头猪无法分进这些猪圈；所有 $a_i$ 两两互质。要求根据这些余数信息，求猪的最少可能数量。

数据规模：$1\le n\le10$，$0\le b_i<a_i\le10^5$，且 $\prod a_i\le10^{18}$。

若猪的总数为 $x$，第 $i$ 次分圈以后剩余 $b_i$ 头，说明 $x \bmod a_{i} = b_{i}$。于是每一次实验都给出了一个关于同一个未知数 $x$ 的余数限制。

这样就得到若干个模数两两互质的同余条件，可以使用中国剩余定理构造公共解。

令总模数为 $M=\prod_i a_i$，并记 $M_i=M/a_i$。由于各个模数两两互质，所以 $\gcd(M_i,a_i)=1$，可以求出 $M_i$ 在模 $a_i$ 下的逆元 $t_i$。

于是每一项 $b_iM_it_i$ 在模 $a_i$ 下等于 $b_i$，而在其他模数下等于 $0$。将这些项相加，就可以构造出一个同时满足全部条件的解。

Q5

P3868 猜数字
给定两组各含 $k$ 个整数的数列 $a_1,\dots,a_k$ 与 $b_1,\dots,b_k$，其中第二组中的 $b_i$ 两两互素。要求找到最小的自然数 $n$，使对于每个 $i$，$n-a_i$ 都能够被 $b_i$ 整除。

数据规模：$1\le k\le10$，$|a_i|\le10^9$，$1\le b_i\le6\times10^3$，且 $\prod b_i\le10^{18}$。

题目给出的条件是整除关系 $b_i\mid(n-a_i)$。改写成模意义下的余数条件，就有 $n-a_i\equiv0\pmod{b_i}$，也就是 $n\equiv a_i\pmod{b_i}$。

于是原问题变成了一个模数两两互质的同余方程组，可以直接使用 CRT。

注：$a_i$ 可能为负数，所以实现时需要先把余数规范化到 $[0,b_i)$。

Q6

P4777 扩展中国剩余定理
给定 $n$ 组整数 $a_i,b_i$，要求找到最小的非负整数 $x$，使得对于所有 $i$，$x$ 除以 $a_i$ 的余数都是 $b_i$。这里不再保证各个模数 $a_i$ 两两互质，但数据保证整个方程组存在公共解。

数据规模：$1\le n\le10^5$，$1\le a_i\le10^{12}$，$0\le b_i\le10^{12}$，所有 $a_i$ 的最小公倍数不超过 $10^{18}$。

本题去掉了 CRT 中最关键的“两两互质”条件，所以没法继续利用“每一项只对一个模数有贡献”的方式直接构造答案。

不过可以换一种思路，只考虑如何合并两个已经得到的解类。对于 $x\equiv a\pmod m$ 和 $x\equiv b\pmod n$，由第一个条件写成 $x=a+mp$，再代入第二个条件，就得到 $mp\equiv b-a\pmod n$。

这就又回到了线性同余方程，令 $g=\gcd(m,n)$，若 $g\nmid b-a$，两个解类没有交集；否则求出 $p$ 的一个解，得到新的基础解 $x_0=a+mp_0$。

合并后的周期是 $\operatorname{lcm}(m,n)$，于是两个同余条件被压缩成一个新的剩余类，接着和下一个条件合并即可。

笔记

exCRT 可以理解为“不断求两个解类的交”。

每次合并内部真正调用的仍然是线性同余，所以它与 CRT 的直接构造实际上是两条不同的求解路径。

同余方程组的识别

如果题目要求同一个未知数同时满足若干周期条件，可以先分别求出每个条件对应的解类。

模数两两互质时可以直接 CRT；不互质时则把两个解类的合并重新化成线性同余，并逐步执行 exCRT。

三、指数同余方程

前两类问题中，未知量通常以线性形式出现。若未知量进入指数位置，标准模型就变成 $a^x\equiv b\pmod m$，此时需要处理离散对数问题。

Q7

P3846 BSGS / 可爱的质数
给定质数 $p$ 和两个整数 $b,n$，要求寻找最小的非负整数 $l$，使 $b^{l} \equiv n \pmod{p}$。若这样的指数不存在，则输出 no solution。

数据规模：$2\le b<p<2^{31}$，$1\le n<p$。

题目已经直接给出了未知指数 $l$，所以它就是离散对数问题最基本的形式。

直接枚举 $l$ 的范围太大，所以考虑把指数拆成两部分。令 $t=\lceil\sqrt p\rceil$，并写成 $l = i \cdot t - j$，那么原式可以改写为 $b^{i \cdot t}\equiv nb^j\pmod p$。

于是可以枚举 $j$，把所有 $n \cdot b^j\bmod p$ 存入哈希表；再枚举 $i$，寻找 $b^{i \cdot t}\bmod p$ 是否已经出现。两边相遇时，就能恢复出对应的指数 $l$。

BSGS 本质上是折半搜索：利用指数相加对应幂相乘，把原本约 $p$ 级别的搜索拆成两个约 $\sqrt p$ 级别的集合。

Q8

P4454 破解 D-H 协议
Diffie-Hellman 协议公开一个质数 $P$ 和模 $P$ 的原根 $g$。Alice、Bob 分别选择秘密整数 $a,b$，并公开 $A=g^a\bmod P$ 与 $B=g^b\bmod P$，双方最终使用 $g^{ab}\bmod P$ 作为共享密钥。现在给出多次通信中被窃听到的 $A,B$，要求恢复每次通信的共享密钥。

数据规模：$2\le A,B<P<2^{31}$，$2\le g<20$，连接次数 $1\le n\le20$。

原根保证 $g$ 能够生成模 $P$ 下的所有非零剩余类，不过实际求解时不需要同时恢复 $a,b$。

根据 $A=g^a\pmod P$，使用 BSGS 求出一个离散对数 $a$，然后计算 $B^a\bmod P$，就能得到共享密钥 $g^{ab}\bmod P$。

因此本题仍然是 BSGS 的直接应用，只是离散对数并非最终答案。

Q9

P4884 多少个 1？
给定整数 $K$ 和质数 $m$，要求找到最小的正整数 $N$，使由 $N$ 个 $1$ 组成的整数模 $m$ 的余数恰好为 $K$，题目保证答案存在。

数据规模：$6\le m\le10^{11}$，$0<K<m$，并保证 $m$ 为质数。

题目中的未知量 $N$ 是十进制数的位数，并没有直接出现在指数上，我们尝试把这个诡异的式子转化为熟悉的样子。

由 $N$ 个 $1$ 组成的整数可以写成 $\displaystyle R_{N} = \frac{10^N - 1}{9}$。由于 $m\ge6$ 且 $m$ 为质数，所以 $m$ 不会整除 $9$ 或 $10$，两者在模 $m$ 下都可逆。

将 $R_N\equiv K\pmod m$ 的两边乘以 $9$，可以得到 $10^N\equiv9K+1\pmod m$，于是转化为以 $10$ 为底的离散对数问题，调用 BSGS 求最小正整数 $N$ 即可。

这里 $m$ 最大达到 $10^{11}$，实现模乘时需要使用 __int128 避免溢出。

Q10

P4861 按钮
一个高精度 $M$ 进制计算器最初显示数字 $1$。每按一次按钮，屏幕上的整个数都会乘以 $K$；当这个 $M$ 进制数的个位再次变成 $1$ 时，房门打开。要求求出最少需要按多少次按钮，若永远无法出现这样的个位则输出指定字符串。

数据规模：$2\le M,K\le2\times10^9$。

按下 $x$ 次以后，屏幕上的整数变成 $K^x$。而一个整数在 $M$ 进制下的个位，恰好就是它模 $M$ 的余数。

所以“个位再次变成 $1$”可以写成 $K^x\equiv1\pmod M$。这仍然是一个指数同余的方程，只不过右端固定为了 $1$。

此时要求的最小正整数 $x$，就是 $K$ 在模 $M$ 意义下的乘法阶。若 $\gcd(K,M)\ne1$，则不可能存在正整数 $x$ 使 $K^x\equiv1\pmod M$；反之可以把它视为右端为 $1$ 的离散对数，继续使用 BSGS 求解。

不过普通 BSGS 会把 $x=0$ 视为 $K^x\equiv1\pmod M$ 的最小非负解，而本题要求的是最小正整数。因此实现时不能在右端为 $1$ 时直接返回 $0$，需要继续寻找碰撞并取最小的正指数。

Q11

P4195 扩展 BSGS
有多组询问，每组给定三个正整数 $a,p,b$，要求找到最小的自然数 $x$，使 $a^x$ 模 $p$ 的余数为 $b$。不保证底数 $a$ 与模数 $p$ 互质；若无解则需要输出 No Solution。

数据规模：$1\le a,p,b\le10^9$，并保证所有测试数据满足 $\sum\sqrt p\le5\times10^6$。

普通 BSGS 依赖底数在模 $m$ 下可逆，所以当 $\gcd(a,m)\ne1$ 时不能直接使用。

令 $g=\gcd(a,p)$。若 $g\nmid b$，当前方程无解；若 $g\mid b$，则可以约去一个公共因子，同时记录已经从左侧消去多少个 $a$，并继续缩小模数。

不断执行这个过程，直到新的底数与模数互质，再转入普通 BSGS。exBSGS 其实也就是先消去不可逆部分，把问题重新化回 BSGS 的适用范围。

指数同余的识别

当未知量直接出现在指数位置，或者经过等比数列、乘法过程等变换后进入指数位置时，可以尝试转成 $a^x\equiv b\pmod m$。

互质情形使用 BSGS；一般情形先通过 gcd 消去不可逆部分，再进入 exBSGS。右端为 $1$ 时，还可以把问题理解为求乘法阶。

四、综合问题

前面的三类问题都已经给出了比较标准的方程形式。不过在实际题目中，更常见的是先经过一段额外的结构处理，才能得到这些标准同余模型。

线性递推中的同余

Q12

P3306 随机数生成器
一本书共有 $p$ 页，页码为 $0$ 到 $p-1$。第 $i$ 天阅读的页码由序列 $x_i$ 决定，其中初值为 $x_1$，以后按照 $x_{i+1}\equiv ax_i+b\pmod p$ 生成。给定目标页码 $t$，要求判断第一次读到第 $t$ 页是第几天；若序列永远不会出现 $t$，则输出 $-1$。

数据规模：$1\le T\le50$，$2\le p\le10^9$ 且 $p$ 为质数，$0\le a,b,x_1,t<p$。

首先直接展开递推。由于初值是 $x_1$，到达第 $i$ 天一共经过了 $i-1$ 次转移，所以有 $\displaystyle x_i\equiv a^{i-1}x_1+b\sum_{j=0}^{i-2}a^j\pmod p$。于是原问题变成：求最小的 $i$，使这个通项在模 $p$ 意义下等于目标值 $t$。

首先检查 $x_1=t$，此时答案就是第 $1$ 天。当 $a=0$ 时，从第 $2$ 天开始序列恒为 $b$，可以直接判断；当 $a=1$ 时，递推退化为 $x_i\equiv x_1+(i-1)b\pmod p$。要求 $x_i=t$，就得到 $(i-1)b\equiv t-x_1\pmod p$，这正是一个线性同余方程。

当 $a\ne0,1$ 时，可以利用等比数列求和，将通项整理为 $\displaystyle x_i\equiv a^{i-1}x_1+b\frac{a^{i-1}-1}{a-1}\pmod p$。由于 $p$ 为质数且 $a\not\equiv1\pmod p$，所以 $a-1$ 在模 $p$ 下存在逆元。

把含有 $a^{i-1}$ 的部分合并，可以写成 $\displaystyle x_i\equiv a^{i-1}\left(x_1+\frac{b}{a-1}\right)-\frac{b}{a-1}\pmod p$。再代入目标条件 $x_i=t$，得到 $\displaystyle a^{i-1}\left(x_1+\frac{b}{a-1}\right)\equiv t+\frac{b}{a-1}\pmod p$。

记 $\displaystyle C=x_1+\frac{b}{a-1}$，$\displaystyle D=t+\frac{b}{a-1}$，那么问题就被压缩成 $a^{i-1}C\equiv D\pmod p$。

若 $C\not\equiv0\pmod p$，则 $C$ 在模 $p$ 下存在逆元，于是可以继续化为 $a^{i-1}\equiv DC^{-1}\pmod p$，化为标准的离散对数问题。使用 BSGS 求出最小非负指数 $k=i-1$ 后，原题答案为第 $k+1$ 天。

若 $C\equiv0\pmod p$，则需要单独判断退化情况。此时左侧恒为 $0$；若 $D\not\equiv0\pmod p$ 则无解，若 $D\equiv0\pmod p$ 则目标从初始状态起就成立，而这一情况已经由 $x_1=t$ 处理。

笔记

这题连接了前面的两类模型：不是因为题面出现递推就使用某个固定算法，而是先求出递推的代数结构，再观察未知下标最终以线性形式还是指数形式出现。

动态约束下的同余方程组

Q13

P4774 屠龙勇士
玩家需要依次击杀 $n$ 条龙。第 $i$ 条龙有初始生命值 $a_i$ 和恢复量 $p_i$；面对它时，机器人会按照固定规则从当前剑集合中选择一把剑，并统一攻击 $x$ 次。攻击结束后，龙会不断恢复 $p_i$ 点生命，只有某次恢复后生命值恰好为 $0$ 才能被击杀。击杀后当前剑消失，同时获得一把新的奖励剑。要求找到能够依次击杀所有龙的最小攻击次数 $x$。

数据规模：$T\le5$，$n,m\le10^5$，$a_i\le10^{12}$，所有武器攻击力不超过 $10^6$，并保证所有 $p_i$ 的最小公倍数不超过 $10^{12}$。

这题不能一开始就列同余方程，因为第 $i$ 条龙实际使用的攻击力并不是固定输入，而取决于此前剑集合的变化。首先要按照题目的选剑规则维护当前武器集合，确定面对每条龙时真正使用的攻击力 $d_i$。

确定 $d_i$ 后，攻击 $x$ 次会造成 $d_ix$ 点伤害。若之后经过若干次恢复恰好回到 $0$，那么伤害超过初始生命值的部分必须能够被 $p_i$ 整除，同时攻击本身至少需要把生命值降到非正数。

于是第 $i$ 条龙同时给出同余条件 $d_ix\equiv a_i\pmod{p_i}$ 和大小条件 $d_ix\ge a_i$。前者是带系数线性同余，后者则不能被 CRT 包含进去。

令 $g_i=\gcd(d_i,p_i)$，若 $g_i\nmid a_i$，这一条同余无解。否则约去 $g_i$，再利用逆元把它化成关于 $x$ 的标准解类，这样所有龙的周期约束才真正形成一个一般同余方程组。

接下来使用 exCRT 合并所有解类，得到最终通解 $x\equiv x_0\pmod M$。与此同时，还要保留由所有龙共同产生的下界 $\displaystyle L=\max_i\left\lceil\frac{a_i}{d_i}\right\rceil$，最后在这个解类中取第一个不小于 $L$ 的整数。

摘要

P4774 的完整规约不是简单的“线性同余 + exCRT”，而是先动态确定方程系数，再把击杀条件拆成“同余约束 + 大小约束”，之后才进入线性同余和 exCRT。

这也说明 CRT / exCRT 只负责合并周期条件，原问题中的其他限制仍然需要单独保留。

五、统一认识

这几类问题表面上对应不同算法，但真正稳定的识别方式，是先观察未知量在方程中的位置，再把题意规约成标准形式。

1. 若两个量随同一个未知参数线性变化，并且要求它们在某个周期意义下相等，可以尝试整理成 $ax\equiv b\pmod m$。

2. 若同一个未知量同时受到多个余数或周期条件限制，可以先得到每个条件对应的解类，再用 CRT 或 exCRT 求这些解类的交。

3. 若未知量位于指数位置，或者能通过等比数列、乘法过程等变换进入指数位置，可以尝试整理成 $a^x\equiv b\pmod m$。

4. 若题面还包含递推、动态选择或大小限制，应先保留这些原始结构，再判断经过变换以后会落入哪一种标准同余模型。

因此，同余类问题的关键通常不是记住更多公式，而是完成“题意 $\to$ 数学关系 $\to$ 标准方程”的规约。标准式确定以后，后半段往往只是调用 exgcd、CRT / exCRT、BSGS / exBSGS 等已有工具。