自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:10:41，当前版本为作者最后更新于2019-06-19 21:56:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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$。

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

---