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

· · 题解

这是一篇基于 FFT 的压 4 位高精度题解（我写的是 loj 版，没有最后的多项式求逆，提交记录（写的巨丑））。

本文大致参考楼下大佬，附蒟蒻自己瞎搞的误差分析。

假设你在 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)