Project Euler 820

题目

$N^{\text{th}}$ digit of Reciprocals

Let $d_n(x)$ be the $n^{\text{th}}$ decimal digit of the fractional part of $x$, or $0$ if the fractional part has fewer than $n$ digits. For example:

• $d_7\left(1\right)=d_7\left(\frac{1}{2}\right)=d_7\left(\frac{1}{4}\right)=d_7\left(\frac{1}{5}\right)=0$
• $d_7\left(\frac{1}{3}\right)=3$ since $\frac{1}{3}=0.333333\mathbf{3}333\dots$
• $d_7\left(\frac{1}{6}\right)=6$ since $\frac{1}{6}=0.166666\mathbf{6}666\dots$
• $d_7\left(\frac{1}{7}\right)=1$ since $\frac{1}{7}=0.142857\mathbf{1}428\dots$

Let ${\displaystyle S(n)=\sum _{k=1}^n{d}_n\left(\frac{1}{k}\right)}$. You are given:

• $S(7)=0+0+3+0+0+6+1=10$
• $S(100)=418$

Find $S({10}^7)$.

解决方案

与第 731 题一样。如果要求分数 ${\displaystyle \frac{a}{b}}$ 的第 $n$ 位后的情况，那么相当于计算分数 ${\displaystyle \frac{a\cdot {10}^{n-1}}{b}}$ 的小数情况。这相当于直接将小数点右移了 $n-1$ 位。

并且我们不需要知道分数 ${\displaystyle \frac{a\cdot {10}^{n-1}}{b}}$ 的整数部分。为了方便计算，就求 ${\displaystyle \frac{a\cdot {10}^{n-1}\mathrm{\%}b}{b}}$ 的小数部分。

令 $x={\displaystyle \frac{a\cdot {10}^{n-1}\mathrm{\%}b}{b}}$，那么 $\lfloor {\displaystyle \frac{10x}{b}}\rfloor$ 就是 ${\displaystyle \frac{a}{b}}$ 第 $n$ 位的小数值。

代码

#include <bits/stdc++.h>
# include "tools.h"
using namespace std;
typedef long long ll;
const int N=10000000;

int main(){
    int ans=0;
    for(int k=1;k<=N;k++){
        int x=qpow(10,N-1,k);
        ans+=x*10/k;
    }
    printf("%d\n",ans);
}