820. 倒数的第N位(Nth Digit of Reciprocals)
设\(d_n(x)\)是\(x\)的小数部分的第\(n\)位数字，如果小数部分不足\(n\)位，则为零。比如：
- \(d_7(1)=d_7(1/2)=d_7(1/4)=d_7(1/5)=0\)
- \(d_7(1/3)=3\)因为\(1/3=0.33333333333...\)
- \(d_7(1/6)=6\)因为\(1/6=0.1666666666...\)
- \(d_7(1/7)=1\)因为\(1/7=0.1428571428...\)
设\(S(n)=\sum_{k=1}^{n}d_n(\frac{1}{k})\)，易得：
- \(S(7)=0+0+3+0+0+6+1=10\)
- \(S(100)=418\)
求\(S(10^7)\)。
分析：设\(r_k=10^n\mod{k}\)，由余数与商的关系有：
$$
\frac{10^{n}}{k} =\left\lfloor \frac{10^{n}}{k}\right\rfloor +\frac{r_{k}}{k}
$$
则对于第\(n\)位小数\(d_n\)，有：
$$
d_{n}\left(\frac{1}{k}\right) =\left\lfloor \frac{10\left( 10^{n}\bmod k\right)}{k}\right\rfloor =\left\lfloor \frac{10r_{k}}{k}\right\rfloor
$$
因此，可以定义：
$$
S( n) =\sum _{k=1}^{n} d_{n}\left(\frac{1}{k}\right) =\sum _{k=1}^{n}\left\lfloor \frac{10\left( 10^{n}\bmod k\right)}{k}\right\rfloor
$$
使用\(python\)的快速幂函数，可以快速的计算出结果，代码如下：
# time cost = 11.9 s ± 120 ms
def sum_of_nth_digit(n=10**7):
total = 0
for k in range(2, n + 1):
r = pow(10, n - 1, k)
total += 10 * r // k
return total