题解 P5432 【A/B Problem (高精度除法)】

这是一篇基于 $FFT$ 的压 4 位高精度题解（我写的是 `loj` 版，没有最后的多项式求逆，[提交记录（写的巨丑）](https://loj.ac/s/1026697)）。 本文大致参考[楼下大佬](https://www.luogu.com.cn/blog/_post/138771)，附蒟蒻自己瞎搞的误差分析。 --- 假设你在 $g$ 进制下进行运算，$a,b$ 在 $g$ 进制下分别有 $n,m$ 位。 考虑这样一件事情： $$ \left\lfloor\dfrac ab\right\rfloor-\left\lceil\dfrac at\right\rceil\le \left\lfloor\dfrac ab-\dfrac at\right\rfloor\le \left\lfloor\dfrac{a\lfloor\frac tb\rfloor}t\right\rfloor\le \left\lfloor\dfrac ab\right\rfloor $$ 因此 $\left\lfloor\dfrac{a\lfloor\frac tb\rfloor}t\right\rfloor$ 与答案的差 $\le \left\lceil\dfrac at\right\rceil$，只需取 $t=g^n>a$ 就能保证误差 $\le 1$，同时方便做除 $t$ 的运算，求出“余数”微调答案即可。 当 $n>2m$ 时，可以将 $a,b$ 同时乘以 $g^{n-2m}$ 使得 $n'\le 2m'$，因此只需求出 $\left\lfloor\dfrac {g^{2m}}b\right\rfloor$ 。 --- 考虑牛顿迭代： 事实上实数求逆的牛迭形如 $x_{n+1}=2x_n-ax_n^2$，考虑仿照这个来。 取 $k$ 为一个 $m/2$ 左右的数，且你已求出 $b$ 的最高 $k$ 位的答案。形式化地说， 设 $c=\dfrac {g^{2m}}b,b'=\left\lfloor\dfrac{b}{g^{m-k}}\right\rfloor,c'=\left\lfloor\dfrac {g^{2k}}{b'}\right\rfloor$ ，你已经知道 $b',c'$，要求 $\lfloor c\rfloor$。 那么迭代得到 $c^*=2c'g^{m-k}-bc'^2g^{-2k}$ 作为 $c$ 的近似值。 设 $c'=\dfrac{g^{m+k}}{b}+\Delta$，则 $c^*$ 的绝对误差为 $$ c-c^*=\dfrac{g^{2m}}{b}-\left(2\dfrac{g^{2m}}{b}+2\Delta g^{m-k}-\dfrac{g^{2m}}{b}-2\Delta g^{m-k}-b\Delta^2g^{-2k}\right)=b\Delta^2g^{-2k} $$ 考虑 $c'$ 的取值范围： $$ \dfrac{g^{m+k}}{b}-1\le \dfrac{g^{2k}}{b'}-1\le c'\le \dfrac{g^{2k}}{b'}\le \dfrac{g^{2k}}{\dfrac{b}{g^{m-k}}-1}=\dfrac{g^{m+k}}{b-g^{m-k}} $$ 因此 $\Delta$ 的取值范围是： $$ -1\le\Delta\le g^{m+k}\dfrac{g^{m-k}}{b(b-g^{m-k})}=\dfrac{g^{2m}}{b(b-g^{m-k})} $$ 所以（$b\ge g^{m-1}$） $$ b\Delta^2 g^{-2k}\le \dfrac{g^{4m-2k}}{b(b-g^{m-k})^2}\le \dfrac{g^{m+1}}{(g^{k-1}-1)^2}=\dfrac{g^{m+1}}{g^{2k-2}-2\cdot g^{k-1}+1}\le \dfrac{g^{m-k+2}}{g^{k-1}-2}=g^{m-2k+3}\left(1+\dfrac{2}{g^{k-1}-2}\right) $$ 当 $g\ge 10$ 时，保守估计误差不超过 $2g^{m-2k+3}$ 。 取 $k=\left\lceil\dfrac{m}2\right\rceil+2$，则 $m+4\le 2k\le m+5$，误差 $\le 2g^{-1}<1$，只需调整至多一次。 --- 至于递归次数，每次 $k\le \dfrac{m+5}2$，所以递归 $x$ 次后 $m'$ 不超过 $\dfrac{m}{2^x}+5$ ，可以当 $m\le 10$ 时直接暴力。 复杂度 $T(n)=T(n/2)+O(n\log n)=O(n\log n)$