# 农务署：题解

## 解法比较

出题人解法把有限小数和循环小数精确化为分数：有限部分使用十的幂作分母，循环部分使用 $10^f(10^r-1)$ ，其中 $f,r$ 是非循环位数和循环节长度。合并后约分，再求全部最简分母的最小公倍数。整数倍条件等价于能被每个最简分母整除，所以下文的证明也适用于出题人解法。

出题人实现自带以 $10^9$ 为基底的大整数和试商除法；Codex（GPT-6）采用的实现改用较直接的十进制大整数运算，明确零、前导零和循环节的解析。两者都采用学校式乘除与欧几里得 GCD；用 $D$ 表示中间整数的最大十进制位数，保守时间上界为 $O(nD^3)$ ，算术工作空间为 $O(D)$ .改变基底会改变常数，不能据此宣称提速；收益是可移植的精确运算与边界说明，数学模型未变。

## 将小数准确化为分数

不能使用浮点数读取比例。设有限部分的小数位数为 $f$ ，循环部分长度为 $r$ .把有限部分的小数点去掉，得到整数 $A$ ；把循环部分接在这些数字后面，得到整数 $B$ .则

$$x=\frac{B-A}{10^f(10^r-1)}$$

证明：$10^f x$ 与 $10^{f+r}x$ 的无限小数尾部相同，相减后得到整数 $B-A$ .该公式也适用于全零循环节、前导零和循环 $9$ .例如 `0.7 142857` 给出 $(7142857-7)/(10(10^6-1))=5/7$ .

用最大公约数约分，得到 $x=u/v$ .当分子为零时，$\gcd(0,v)=v$ ，约分后的分母自然为 $1$ .

## 总量是分母的最小公倍数

因为 $u,v$ 互质，$Hx$ 为整数当且仅当 $v\mid H$ .因此答案为所有最简分母的最小公倍数，逐项更新：

$$H\leftarrow\frac{H}{\gcd(H,v)}\,v$$

这个条件也足够：已知作物数量均为整数，总和不超过 $H$ ；剩余数量 $H-\sum_i Hr_i$ 也是非负整数，可分配给未公布的作物。初始 $H=1$ ，依次更新后得到最小可行正整数。

## 高精度实现

答案可能远超 64 位。参考程序仅用标准 C++17，实现非负十进制大整数的比较、减法、乘法、商和余数，无需外部大整数库。

长除法从高位逐位读入被除数。每读一位，余数乘以十再加这一位，反复减去除数得到当前商位。旧余数小于除数，所以新商位最多为九，循环不会随数值大小线性增长。除法只用于非零除数；欧几里得算法先判断第二个数是否为零。

设 $D$ 为计算过程中大整数的最大十进制位数，$L$ 为单个比例的最大输入长度，则 $D=O(nL)$ .朴素乘法和单次长除法的时间均为 $O(D^2)$ .欧几里得算法每两轮至少将较大参数缩小一半，因此最多 $O(D)$ 轮，可得整体的保守时间上界 $O(nD^3)$ ，空间 $O(D)$ .这里把位数保留为参数，不把本题的长度上限代入复杂度。

## 验证

独立实现以 Python 精确分数把有限前缀与循环几何级数分别相加，再计算分母的最小公倍数。所有正式输入也以该实现核对答案，覆盖零比例、循环九、重复循环节、长有限部分及长循环部分。

## 程序与复现

参考程序见 [std.cpp](std.cpp)。使用 C++17 编译后，可用 `tests/generate.py --out-dir <题目目录以外的路径> --std <程序路径>` 生成输入和答案。固定种子与用例目的见 [生成计划](tests/plan.json)。性能测量见 [评测环境与性能](../../../docs/评测环境与性能.md)。