UVa 10866 Magic Bitstrings这道题在 OJ 界流传了十几年网络上的题解数量却一直不多。第一次见到它的人多半会被题目里那个 Magic 的定义绕晕长度 n 的 01 串下标之间满足某种乘法同余关系时对应位必须相同。听起来很抽象但把约束翻译成 gcd 之后就只剩一件事给每个等价类涂颜色。这篇文章我会把从题面到数学模型的完整推导过程写清楚再给出一版可以直接提交的构造代码最后聊聊这两年我在 WSL2 里复现老 UVA 题目时踩过的环境坑包括那个烦人的 uva is not available。适合刚接触数论构造题、或者想在本地把老题跑通的读者。1. Magic 的约束到底是什么1.1 题面里的乘法同余究竟想表达什么老 OJ 上的题面通常很短大意是给定正整数 n构造长度为 n 的 01 串 s使得当下标之间存在某种“乘法关系”时对应位置必须取相同的字符。不同平台上对 Magic 的提法不完全一样有的说“当 a/b 等于 c/d 时”有的说“当存在 k 使得 i*k ≡ j (mod n) 时”但几乎所有题解最终都收敛到同一个核心模型所有满足 gcd(i, n) gcd(j, n) 的下标 i 和 j必须填写相同的 bit。先别急着质疑为什么跳过题目原文直接给结论。这个模型的推导其实很自然而且比死记结论重要得多。假设存在乘数 k1 和 k2使得i * k1 ≡ j (mod n)j * k2 ≡ i (mod n)也就是说 i 和 j 在模 n 乘法意义下互相可达。字符串里的相等关系是双向的所以只有这种“双向可达”的下标对才会被约束强制同色。如果只是单方向 i 能到 j约束本身并不对称讨论起来会退化得很厉害这也是为什么我在前面强调“互相可达”这个前提。为什么是 gcd核心在于一个简单的整除观察如果 i * k ≡ j (mod n)那么 j 和 i * k 在模 n 意义下同余于是 gcd(i * k, n) gcd(j, n)。而 gcd(i, n) 一定整除 i * k 和 n所以 gcd(i, n) 整除 gcd(j, n)。反过来如果 j 也能到达 i又能得到 gcd(j, n) 整除 gcd(i, n)。两个方向一夹gcd 只能相等。反过来如果 gcd(i, n) gcd(j, n) d那么线性同余方程 i * x ≡ d (mod n) 一定有解因为 gcd(i, n) d 整除 d同样可以找到 y 使得 d * y ≡ j (mod n)。于是 i → d → j 构成一条合法路径。这就证明了等价类完全由 gcd(i, n) 决定一个不多一个不少。用个生活化的类比把下标想象成不同楼层gcd(i, n) 相同的楼层之间有一部专属电梯你只能在同组楼层之间来回永远到不了别的 gcd 组。所以问题的自由度根本不在 n 个位置而在 n 的约数个数上。1.2 建模完成后题目变成了什么一旦知道等价类是按 gcd(i, n) 划分的问题瞬间就简单了。n 的每个正约数 d 对应一个等价类d 1所有与 n 互质的 i即 gcd(i, n) 1 的位置d p所有含因子 p 且其他因子与 n 互质的位置……d n只包含下标 0因为 gcd(0, n) n。每个等价类内部必须同色不同等价类之间没有任何强制关系。所以可行的 01 串总数是 2^τ(n)其中 τ(n) 是 n 的正约数个数。下标 0 单独一组这件事也很重要它保证了 n 1 时一定存在既不全 0 也不全 1 的构造让第 0 位是 0让 gcd 为 1 的那一组是 1 即可。这里有个容易忽略的边界n 1 时下标只有 0gcd(0, 1) 1等价类也只有一个输出 0 或 1 都合法。很多老题的隐藏数据都会卡这种极端情况所以实现时第一件事就是处理 n 1。2. 先打表观察再总结规律2.1 写一个快速验证脚本在推导出上面的模型之后我习惯先用一段很短的程序把 n 很小的情况全部打出来看看输出长什么样心里有个底。用 Python 只需要十几行import math def solve(n): s [0] * n for i in range(n): if math.gcd(i, n) 1: s[i] 1 return .join(s) for n in range(1, 17): print(n, solve(n))这里用了一个具体的着色规则gcd(i, n) 为奇数时填 1否则填 0。它天然满足同一等价类内同色因为同一组里的 gcd 完全相等奇偶性当然也相等。打表不是为了找唯一解而是为了观察一个合法解的存在形态。2.2 打表结果里能读到什么上面脚本在 n 1..16 时的输出大概是这样的n构造串等价类数量 τ(n)101201230112401013501111260101014701111112801010101490111111113100101010101411011111111112120101010101016130111111111111214010101010101014150111111111111114肉眼一看规律其实很明显当 n 是奇数时除了第 0 位剩下的位置 gcd(i, n) 全是奇数所以输出从0111开始当 n 是偶数时gcd 是否为奇数完全由 i 的奇偶性决定奇数 i 填 1偶数 i 填 0于是输出变成 01 交替。这说明我们甚至可以绕过每次求 gcd直接用 O(1) 的规则生成答案n 为奇数答案 0 1 * (n - 1)n 为偶数答案 01 * (n // 2)这个结论正确性很好证n 为奇数时不存在偶因子任意 gcd(i, n) 都不可能是偶数n 为偶数时gcd(i, n) 为偶数当且仅当 i 是偶数所以按奇偶交替填位即可。我第一次看到这个后门时还挺意外的构造题经常藏着这种“代码越短越有含金量”的规律。2.3 等价类数量决定了题目的难度上限注意到 τ(n) 是 n 的约数个数它通常远小于 n。n 12 时约数只有 6 个等价类也只有 6 组但长度却有 12。这意味着真实的信息量并不在字符串本身而在 n 的因子结构上。这也是这类题适合放进算法竞赛的原因它考察的是建模能力而不是输出能力。有些资料会把这类题归类为“找规律”但靠肉眼凑答案是极度不可靠的。我个人的建议是先证明约束的等价类结构再打表验证直觉最后才谈实现。顺序反了的话很容易被几个小数据带偏造出一个看似对、实则违法的串。3. 提交级实现代码与正确性证明3.1 老 OJ 的输入输出约定网上流传的 UVA 10866 输入通常约定为多组数据每行一个整数 n以 0 结束。每组输出一行构造好的 01 串行尾带换行。没有特别说明的话不要在组与组之间打印空行更不要打印 Case # 之类的前缀。老题的 checker 通常只检查合法性不接受额外的提示字符。我用 C 写过一版稳定的提交代码构造规则就是用 gcd 奇偶性分色。为了兼容老编译器我手写了一个 gcd 函数没用 C17 的 std::gcd也没用 GNU 的 __gcd因为部分老环境对后者的支持并不一致#include cstdio #include string using namespace std; int gcd_int(int a, int b) { return b 0 ? a : gcd_int(b, a % b); } int main() { int n; while (scanf(%d, n) 1 n) { string s(n, 0); for (int i 1; i n; i) { int g gcd_int(i, n); if (g 1) s[i] 1; } puts(s.c_str()); } return 0; }如果你确定本地是较新的编译器也可以用 __gcd 或者 std::gcd但老题提交时我一般会用最保守的写法毕竟谁也不想因为一个标准库函数版本问题白交一发 WA。3.2 正确性拆解这段代码的正确性可以从三个层面看必要充分性第 1 节已经证明Magic 约束等价于“gcd(i, n) gcd(j, n) 时 s[i] s[j]”。所以任何满足这个分组条件的串都合法。构造合法性gcd(i, n) gcd(j, n) 时两者的 gcd 值完全相同奇偶性自然一样因此 s[i] 和 s[j] 的颜色一致。这确保了不会出现组内分裂的情况。边界完整性下标 0 的 gcd 是 n不会被循环里的 i 1..n-1 误染色默认填 0等价类完整。更严格地说我们构造的串未必是“最丰富”的答案但题目只要任意一个合法解所以越朴素越安全。这就像面试里让你写一个排序你不需要写 TimSort老老实实快排或者归并就够了忌讳画蛇添足。3.3 复杂度与进一步优化每次求 gcd 是 O(log n)总共 n 次所以单组数据的时间是 O(n log n)。当 n 上限来到 10^6 时大约两千万次取模运算本地一秒多能跑完老 OJ 如果时限比较紧会有一点风险。真到了需要优化的时候刚才的 O(1) 规律就派上用场了。n 为奇数时直接输出 0 一串 1n 为偶数时输出 0101...。这样复杂度降到 O(n) 输出本身甚至可以说是 O(n) 的 IO 边界决定的下界。代码可以简化成if (n 1) { puts(0); // 后面跟 n-1 个 1 for (int i 1; i n; i) putchar(1); putchar(\n); } else { for (int i 0; i n; i) putchar((i 1) ? 1 : 0); putchar(\n); }不过不建议一上来就写这个“最优版”。先写清晰的 gcd 版本确认思路没问题再考虑常数优化这样的节奏不容易出错。3.4 Python 版用于本地验证Python 版适合在本地快速验证小数据和做对拍但不建议直接提交到老 OJ因为 Python 的启动和循环开销在大 n 下会吃亏。本地验证建议这样写import sys, math def gen(n): s [0] * n for i in range(1, n): if math.gcd(i, n) 1: s[i] 1 return .join(s) def main(): out [] for line in sys.stdin: n int(line.strip()) if n 0: break out.append(gen(n)) sys.stdout.write(\n.join(out) \n) if __name__ __main__: main()这段代码直接对接 C 版跑出来的结果应该完全一致适合做交叉验证。4. WSL2 下复现 UVa 老题从 uva is not available 说起4.1 遇到报错先别慌分清来源最近不少朋友习惯在 WSL2 里做 UVa 老题因为 Windows 侧的文件系统权限和路径分隔符容易出各种幺蛾子。我也在 WSL2 里搭过一套本地验证环境期间就遇到过这类提示“uva is not available”。第一次看到它我下意识以为是网络问题折腾了半天发现根本不是。这类 “not available” 提示第一件事不是重装工具而是搞清楚它到底来自哪里。如果是在终端敲某个命令时直接出现的 command not found那是 PATH 没配好如果是一个旧脚本跑到一半输出的内部日志那通常是脚本依赖的 Python2、Perl 或者某个库不存在如果是连接在线评判网站时弹出的提示那才轮到网络环节去排查。4.2 按顺序排查的四板斧我在本地排查这类问题时基本按下面这张表来现象大概率原因处理动作命令找不到PATH 未配置 / 软件未安装检查 which 目标命令脚本运行到一半退出解释器缺失或版本太旧查看脚本第一行 shebang编译时报 “not available”缺少 multilib 或依赖库安装 g-multilib连接在线服务失败DNS 或网络连不通用 curl 看状态码如果脚本是旧工具包的一部分项目里通常有 README 或者 install.sh先读一遍它里面写的依赖项往往能直接定位。WSL2 默认是不带 Python2 的很多 2010 年前后的辅助脚本都依赖它装一下再跑就正常了。4.3 一套可落地的本地测试脚本无论题目本身多简单我都强烈建议准备一个测试脚本把“编译-运行-比对”三步固化下来不然在多组样例上来回调命令很容易手滑。下面这个脚本放在 ~/uva/10866 目录下#!/bin/bash g -stdc17 -O2 -Wall sol.cpp -o sol if [ $? -ne 0 ]; then echo compile error exit 1 fi ./sol in.txt myout.txt if diff -w myout.txt out.txt; then echo AC else echo WA fi这里的 diff 用了 -w 参数会忽略行尾空白和空格的差异。老题的输出格式有时会在换行符上做文章用 -w 能过滤掉这类与算法无关的差异。不过要提醒一句这只适用于本地自测OJ 的 checker 是否忽略空白取决于题目说明不能一概而论。还有一点经验把工作目录放在 Linux 文件系统里比如 ~/uva不要放在 /mnt/c 下。WSL2 对 /mnt/c 的跨文件系统 IO 和 inotify 支持一直有性能损耗而且部分脚本在挂载的 Windows 分区上会遇到权限判断异常表现为“明明存在却打不开”之类的怪问题。把文件放在 ext4 原生目录里能少踩一半坑。4.4 补齐环境后的运行心得把依赖补齐、脚本写好之后整体的开发体验其实很顺。compile 一条命令跑样例一条命令比对一条命令。遇到 WA 再打开 in.txt 手调反复循环。这套流程放到任何老 OJ 题目上都适用不只是 UVa 10866。关于 “uva is not available” 这类提示最后再多说一句如果排查完确认不是解释器、不是路径、不是权限那再看网络。但绝大多数情况下它跟真正的网络链路没关系只是本地环境里某个组件没齐。先查本地再查外部这个顺序能帮你省下很多无意义的等待时间。5. 常见 WA/TLE 与调试思路5.1 最容易出事的边界数据n 1 时只有下标 0gcd(0, 1) 1等价类只有一个输出 0 合法输出 1 也合法。我用默认构造输出 0没问题。n 2 时两组下标 0 一组下标 1 一组。输出 01、10、00、11 全都合法。我的代码输出 01过样例。n 是素数时最有迷惑性除了第 0 位其余 n - 1 个位置全部属于 gcd 1 的等价类必须同色。所以类似 010101 这种交替串在素数 n 下是违法的除非它恰好没用交替规则。我见过有人把 n 5 的答案写成 0101这就是典型的没注意等价类合并。n 是 2 的幂时等价类数量是 log2(n) 1gcd 分组非常细但我的奇偶构造仍然合法只是会输出成 0101 交替。这再次说明等价类越细可用的合法串反而越多我们无需刻意利用全部自由度。5.2 输出格式的三类经典坑老 UVA 题的输出格式坑比算法坑还多组与组之间到底要不要空行以题目描述为准。没提就绝不输出空行否则一定 WA。行尾换行符要保留。puts 和 Python 的 print 都默认带换行没问题但如果你用 printf 拼接很容易漏掉最后一行的换行。不要输出额外提示。就算你本地测试时觉得加个 Case 1: 可读性好OJ 也不会领情它只会把多出来的字符当成错误输出。我自己的习惯是写完代码后用 od -c 看一眼输出文件里每个字节到底是什么样能直观发现多余空格或缺失换行。这比肉眼盯着终端判断可靠得多。5.3 “任意合法解”的语义陷阱题目允许任意合法解意味着不需要求字典序最小不需要保证 0 和 1 的数量平衡不需要让串看起来随机。我见过一种很常见的错误有人会在构造时试图让串“更美观”比如从 0 开始交替 010101结果反而踩了等价类的坑。本质上只要满足“同 gcd 同色”就必过。你可以全 0也可以全 1或者像我这样按奇偶分色。正因为限制极其宽松任何绕过等价类约束的“优化”都是在给自己找麻烦。5.4 TLE 的常见来源与解决办法如果 n 特别大比如到 10^7每次 for 循环里算 gcd 的常数是主要开销。建议把循环里的 gcd 计算换成前面说的 O(1) 奇偶判断直接生成交替串速度快出一个量级。另一种做法是先用欧拉筛预处理每个数的最小质因子再用质因子集合判断 gcd 的奇偶性但这样反而复杂了。在构造题里能用数学规律化简的就不要上数据结构。时间复杂度 O(n) 且没有额外空间通常已经是这类输出题的最优复杂度因为答案本身就有 n 个字符输入输出就占满了时间。5.5 我后来沉淀下来的做题清单现在我做这类老题固定流程是这样推导约束的等价类写成清晰的数学结论用 Python 打表验证小 n 的构造写 C 版提交到本地脚本自测对拍几组随机数据确认 Python 与 C 输出一致再考虑优化和边界。这套流程说起来平淡但确实帮我避开了大多数不必要的 WA 和 TLE。尤其是第一步把“Magic 约束”翻译成“gcd 分组”的那一瞬间这道题的实际代码量就只剩二十行了。我个人在实际操作中最深的体会就是这类题目代码三分钟推导三小时是常态但推导清楚了后面几乎不会出错。最后再分享一个小技巧如果你在 WSL2 里反复遇到环境类的 “not available” 提示别急着重装系统先看脚本依赖、再看路径、再看网络。把这三板斧练熟了老题环境问题基本都能在十分钟内解决。