自动搬运

查看原文

来自洛谷，原作者为

	5k_sync_closer 数据结构真可爱。

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

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

以下是正文

---

不知道为啥别的题解直接就快速幂了……感觉这个不容易看出

小数点后第 $n$ 位就是把小数点往后移 $n$ 位后的个位。

根据小学数学知识，把一个数的小数点往后移 $n$ 位相当于把这个数乘以 $10^n$。

所以 $\dfrac ab$ 的第 $n$ 位即为 $\dfrac{a\times 10^n}b$ 的个位，即 $\lfloor\dfrac{a\times 10^n}b\rfloor\bmod 10$。

推式子：

$$\begin{aligned} &\lfloor\dfrac{a\times 10^n}b\rfloor\bmod 10\\ =&\lfloor\dfrac{a\times 10^n}b\rfloor-10k\bmod 10\\ =&\lfloor\dfrac{a\times 10^n-10bk}b\rfloor\bmod 10\\ =&\lfloor\dfrac{a\times 10^n\bmod 10b}b\rfloor \end{aligned} $$

快速幂算分子即可。

注意 $10b>2^{32}$，需要龟速乘或者开 __int128。

#include <cstdio>
__int128 P(__int128 x, __int128 y, __int128 M)
{
    __int128 q = 1;
    for (; y; y >>= 1, x = x * x % M)
        if (y & 1)
            q = q * x % M;
    return q;
}
__int128 a, b, n;
int main()
{
    scanf("%lld%lld%lld", &a, &b, &n);
    for (__int128 i = n; i < n + 3; ++i)
        printf("%lld", a * P(10, i, 10 * b) % (10 * b) / b);
    return 0;
}