专栏文章

双模数结构、周期引理和同余最短路

AAugust_Light
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minheour
此快照首次捕获于
2025/12/02 02:27
3 个月前
此快照最后确认于
2025/12/02 02:27
3 个月前
查看原文
提示：本文和双模数 hash 没有关系。

双模数结构

P5330 [SNOI2019] 数论
给出正整数 p,q,Tp,q,T 和整数集 A,BA,B，请你求出：
∑i=0T−1[(i mod p)∈A∧(i mod q)∈B]\sum_{i=0}^{T-1}[(i \bmod p) \in A \land (i \bmod q) \in B]
p,q≤106p,q \le 10^6，T≤1018T \le 10^{18}。
我们不关心这题的具体做法，只讲怎么刻画条件。怎么处理 x mod px \bmod p 和 x mod qx \bmod q 同时出现的式子？
考虑固定 x mod qx \bmod q。对于 [0,q)[0,q) 每个数建一个点，每个点 ii 连边到 (i+p) mod q(i + p) \bmod q，则可以证明：整张图是 gcd⁡(p,q)\gcd(p,q) 个环，每个环环长为 qgcd⁡(p,q)\frac q {\gcd(p,q)}。
通过这样的结构，我们可以把二维的双模数问题，转化为  mod q\bmod q 下的一个环上问题。

WPL 与 PL

弱周期引理 WPL 和周期引理 PL 都是字符串题目中常见的套路。并且这篇文章后面的部分揭示了 PL / WPL 和双模数结构的强关联。
  • 弱周期引理 Weak Periodicity Lemma (WPL)：pp 和 qq 是 SS 的 period 且 p+q≤∣S∣p + q \le \lvert S \rvert，则 gcd⁡(p,q)\gcd(p, q) 也是 SS 的 period。
  • 周期引理 Periodicity Lemma (PL)：pp 和 qq 是 SS 的 period 且 p+q−gcd⁡(p,q)≤∣S∣p + q - \gcd(p, q) \le \lvert S \rvert，则 gcd⁡(p,q)\gcd(p, q) 也是 SS 的 period。
    • p+q−gcd⁡(p,q)p + q - \gcd(p,q) 这个下界是紧的，无法继续加强，∣S∣\lvert S \rvert 再小就有反例了。

证明

像并查集一样，连边 i→i+pi \to i+p 和 i→i+qi \to i+q。但是直接这么考虑不太行。
学习上面的思路，在  mod q\bmod q 下看待这个问题，即我们合并所有  mod q\bmod q 下相等的点。此时 i→i+qi \to i + q 的边天然成立了；剩余每条边形如 i→(i+p) mod qi \to (i + p) \bmod q。
一开始有 qq 个点，最后要连成 gcd⁡(p,q)\gcd(p,q) 个连通块，至少要连 q−gcd⁡(p,q)q - \gcd(p,q) 条边。我们已经证明过了最终是个环结构，因此每条边都不浪费（浪费的定义是，一条边连的两点早就连通了）。
我们连的最后一条边在原图上对应的是 q−gcd⁡(p,q)→p+q−gcd⁡(p,q)q - \gcd(p,q) \to p + q - \gcd(p,q)。因此对于 PL，最小的字符串长度是 p+q−gcd⁡(p,q)p + q - \gcd(p,q)。这也说明了为什么这个界是紧的，因为更少的边根本没办法让连通块只剩 gcd⁡(p,q)\gcd(p,q) 个。
PL 对应的图上，每个本应该是环的连通块事实上缺了一条边，每个连通块都是一条链。若再多花 gcd⁡(p,q)\gcd(p,q) 条边，即字符串长度达到 p+qp+q 时，每个连通块被补全成为完整的环。这也就是 WPL 对应的图。

双模数同余最短路

P3951 [NOIP 2017 提高组] 小凯的疑惑
给定正整数 p,qp,q，保证 p⊥qp \perp q 且 p,q≥2p,q \ge 2。求不能被表示为 xp+yqxp+yq（x,y≥0x,y \ge 0）的最大正整数。
我们在  mod q\bmod q 下看。连边 i→(i+p) mod qi \to (i+p) \bmod q 权值 pp。00 号点到每个点 ii 的单源最短路 disidis_i，即为  mod q\bmod q 下所有可以拼出的数的最小值，比它大的 disi+kqdis_i + kq（k≥0k \ge 0）都可以拼出。
而根据前面的结论，这张图形成一个环，最远的点是走 q−1q-1 步走到的点 p(q−1) mod qp (q-1) \bmod q，最短路为 p(q−1)=pq−pp (q-1) = pq - p，即这个同余类中可以表示出的最小值是 pq−ppq-p。
因此，表示不出的最大数要再减 qq，是 pq−p−q\boxed{pq - p - q}。这个结论在国外被称为 Chicken McNugget Theorem。

多模数同余最短路

多模数没有双模数的优秀性质了，建出的图很乱。
P3403 跳楼机
给定 x,y,zx,y,z，求出 [1,n][1,n] 中有几个数可以被表示成 ax+by+czax+by+cz（a,b,c≥0a,b,c \ge 0）的形式。
x,y,z≤105x,y,z \le 10^5，n≤263−1n \le 2^{63} - 1。
在  mod x\bmod x 下看，连边 i→(i+y) mod xi \to (i + y) \bmod x 边权 yy 和 i→(i+z) mod xi \to (i + z) \bmod x 边权 zz。一样的最短路，使用 Dijkstra 在 O(xlog⁡x)O(x \log x) 的时间求解。
小技巧：由于 x,y,zx,y,z 对称，选择一个最小的作为模数，可以减小常数。
2023 AMC 12B Problems/Problem 16
In the state of Coinland, coins have values 6,10,6,10, and 1515 cents. Suppose xx is the value in cents of the most expensive item in Coinland that cannot be purchased using these coins with exact change. What is xx?
在  mod 6\bmod 6 下看，连边 i→(i+10) mod 6i \to (i + 10) \bmod 6 边权 66 和 i→(i+15) mod 6i \to (i + 15) \bmod 6 边权 1515。模拟 Dijkstra 可以算出最长的最短路是 3535，35−6=2935 - 6 = \boxed{29}。

写在后面

练习题

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...