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 \mathopen{}\left( 1 \right)\mathclose{} = d_7 \mathopen{}\left( \frac 1 2 \right)\mathclose{} = d_7 \mathopen{}\left( \frac 1 4 \right)\mathclose{} = d_7 \mathopen{}\left( \frac 1 5 \right)\mathclose{} = 0\)
• \(d_7 \mathopen{}\left( \frac 1 3 \right)\mathclose{} = 3\) since \(\frac 1 3 = 0.333333{\color{red}{\mathbf{3}}}333\dots\)
• \(d_7 \mathopen{}\left( \frac 1 6 \right)\mathclose{} = 6\) since \(\frac 1 6 = 0.166666{\color{red}{\mathbf{6}}}666\dots\)
• \(d_7 \mathopen{}\left( \frac 1 7 \right)\mathclose{} = 1\) since \(\frac 1 7 = 0.142857{\color{red}{\mathbf{1}}}428\dots\)

Let \(\displaystyle S(n) = \sum_{k=1}^n d_n \mathopen{}\left( \frac 1 k \right)\mathclose{}\). You are given:

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

Find \(S(10^7)\).

解决方案

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

并且我们不需要知道分数\(\dfrac{a\cdot10^{n-1}}{b}\)的整数部分。为了方便计算，就求\(\dfrac{a\cdot10^{n-1}\%b}{b}\)的小数部分。

令\(x=\dfrac{a\cdot10^{n-1}\%b}{b}\)，那么\(\left\lfloor\dfrac{10x}{b}\right\rfloor\)就是\(\dfrac{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);
}