题解 P5432 【A/B Problem (加强版)】

· · 题解

update：修整了一下题解格式。

看看题目让我们求什么：\lfloor a/b \rfloor

我们可以考虑求出 b 的倒数，然后再乘上 a，得出结果。
高精度实数运算实现起来并不复杂，每个数记一下乘了 10 的多少次方，做加减的时候移位一下就行。
做乘法会更简单，不用移位，把幂次加起来即可。

关于怎么求 b 的倒数，可以考虑牛顿迭代：

x-\frac1b=0 x_{i+1}=2x_i-bx_i^2

这里只用到了乘法和减法，所以可以直接用 \Theta(n\log n) 的乘法来算（这里设 a 的位数为 n）。
一般把 x 的初值选为 10^{-\lfloor \lg b \rfloor} 左右的数，这样减小一些常数（一次迭代）。

由于每次迭代精度翻一倍，所以时间复杂度为

T(n)=T(n/2)+\Theta(n\log n)=\Theta(n\log n)

由于 \lfloor a/b \rfloor 的位数最多不超过 n，故计算 1/b 的误差只要小于 10^{-n}，a\times (1/b) 的误差就小于 1，直接取整就得到了 \lfloor a/b \rfloor。

别忘了还要对最后算出来的结果用【模板】多项式求逆 处理一下。

上述做法需要实现高精度实数运算，可能稍微有些麻烦。在 WC2012 的论文《理性愉悦：高精度数值计算》（原作者：倪泽堃）中有提到一种只用高精度整数的做法，这里复述一下：

设 b 有 n 位，那么我们希望求得 b'=\lfloor 10^{2n}/b\rfloor，然后计算出 \lfloor ab'/10^{2n}\rfloor，经调整后即得到 \lfloor a/b\rfloor。
不过这里面有个 b' 舍入的误差问题，为了保证最后调整的次数是 \Theta(1) 的，那么 b 相对 a 的位数不能太少。
假设 a 有 m 位，我们需要使得 m\le 2n。这样可以证明最后调整时，误差不超过10。这很简单，假设 m>2n，两者同时左移若干位即可。

下面的问题就是求解 \lfloor10^{2n}/b\rfloor。设前一次迭代求解的是 b_k'=\lfloor10^{2k}/b_k\rfloor（其中 b_k 为 b 的前 k 位组成的数），那么这一次的迭代式为：

b'^*/10^{2n}=2b_k'/10^{2k}/10^{n-k}-b(b_k'/10^{2k}/10^{n-k})^2

也就是：

b'^*=2b_k'\times10^{n-k}-bb_k'^2/10^{2k} \approx 2b_k'\times10^{n-k}-\lfloor bb_k'^2/10^{2k} \rfloor

求得 b'^* 当然还没完，这只是迭代的结果，不是 \lfloor 10^{2n}/b \rfloor 的精确值。
误差分析表明，当 k>n/2 时，误差不超过 100，于是还要在求得余数 10^{2n}-bb'^* 后对 b'^* 进行 \Theta(1) 次的调整（为了降低常数，还可以二分误差）。这样就迭代求出了 \lfloor 10^{2n}/b \rfloor
迭代边界为 n\le 2，此时 b 在小整数范围内，可以直接求解。

求解出 \lfloor 10^{2n}/b \rfloor 后与 a 相乘，在计算出余数后和上面类似的调整，即可求解出\lfloor a/b \rfloor。

时间复杂度分析同高精度实数做法。