数据恢复题解¶

解法署名：出题人解法通过一个足够大的模数恢复缺失前缀；Codex（GPT-6）采用双模数与中国剩余定理实现精确整数恢复。

解法比较¶

出题人解法：一个足够大的模数¶

设后缀字符串长为 \(k\) 、表示整数 \(s\) ，缺失前缀为 \(x\) ，则 \(n!=x10^k+s\) ，且 \(0\le x<10^{15}\) .出题人解法取质数 \(M=7\cdot2^{52}+1=31525197391593473\) ，分别计算阶乘和后缀的余数，再求

\[ x\equiv(n!-s)(10^k)^{-1}\pmod M \]

因为 \(M\) 与 \(10\) 互质，逆元存在；又因为 \(x<M\) ，正规化后的余数就是完整前缀，无须枚举。前缀非零时先输出前缀，再原样输出后缀。出题人实现用费马小定理和快速幂求逆元。单次精确模乘按常数时间计算时，时间为 \(O(n+k+\log(k+1)+\log M)\) ，保存后缀需 \(O(k+1)\) 空间。

Codex 采用的双模数方案¶

双模数方案同样通过模运算恢复短前缀，使用两个较小质数，再由中国剩余定理合并。单模数方案需要精确模乘：不能直接计算可能超出有符号 64 位范围的乘积，浮点估商也须有严格的误差处理。使用正确模乘时，单模数方案有效。

Codex 实现的模乘及合并中间量均可证明落在有符号 64 位范围内，便于用标准 C++17 精确实现。代价是计算两套余数并增加一次合并；渐进复杂度没有改善，也没有两种实现的直接计时对照。下文给出双模数方案的具体步骤。

只恢复缺失的前缀¶

设输入后缀表示的整数为 \(s\) ，其字符串长度仍保留为 \(k\) .存在非负整数 \(x\) ，使得

\[ n!=x\cdot10^k+s \]

缺失部分至多有十五位，因此 \(0\le x<10^{15}\) .直接生成整个阶乘需要高精度乘法，但只要求出这个较短的前缀即可。

两个模数下求前缀¶

取两个不同质数 \(p=1000000007\) 、\(q=1000000009\) .它们都与 \(10\) 互质，且 \(pq>10^{15}\) .

对模数 \(t\in\{p,q\}\) ，依次相乘计算 \(n!\bmod t\) ；逐位扫描后缀，按“当前余数乘十加新数字”求 \(s\bmod t\) .用快速幂求 \(10^k\bmod t\) ，再用费马小定理计算其逆元，得到

\[ r_t=(n!-s)(10^k)^{-1}\bmod t \]

所有余数都正规化到 \(0,\ldots,t-1\) .输入中的前导零不影响取模，但必须保留在最终拼接的字符串中。

合并与唯一性¶

先令 \(x=r_p+pu\) ，再使它满足模 \(q\) 的条件：

\[ u=(r_q-r_p)p^{-1}\bmod q \]

取 \(0\le u<q\) ，即可得到 \(0\le x<pq\) 内唯一满足两个同余式的数。真实前缀满足这些同余式，且严格小于 \(10^{15}<pq\) ，所以恢复结果必然是真实前缀。

若 \(x>0\) ，先输出它，再原样输出后缀；若 \(x=0\) ，只输出后缀。合法输入中，\(x=0\) 意味着整个阶乘已经在后缀中，不会产生额外前导零。当 \(k=0\) 时，后缀为空且 \(s=0\) ，直接输出恢复的阶乘。\(0!\) 和 \(1!\) 的连乘初值都是 \(1\) .

实现与复杂度¶

设 \(P=\max(p,q)\) .在这些模数可用机器整数表示的模型下，时间为 \(O(n+k+\log(k+1)+\log P)\) ，空间为 \(O(k+1)\) .保存后缀是为了输出；参考程序不构造大整数阶乘。

模乘的两个因子都小于 \(P\) ，乘积小于 \(P^2<2^{63}\) ；中国剩余定理的合并结果小于 \(pq<2^{63}\) .因此标准 C++17 的有符号 64 位整数足够，不需要浮点近似或编译器扩展。

验证¶

小规模使用 Python 的整数阶乘直接比较完整输出；正式输入也逐字与整数阶乘比较。覆盖 \(k=0\) 、\(k=D\) 、最大十五位前缀、后缀前导零和最大 \(n\) .

性能测量见评测环境与性能。

数据恢复 题解¶