P8652 [蓝桥杯 2017 国 C] 小数第 n 位 题解

· · 题解

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

小数点后第 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;
}