# 数据恢复 题解

解法署名：出题人解法通过一个足够大的模数恢复缺失前缀；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$ .

性能测量见[评测环境与性能](../../../docs/评测环境与性能.md)。