Project Euler 40

题目

Champernowne’s constant

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021...

It can be seen that the \(12\)^th digit of the fractional part is \(1\).

If \(d_n\) represents the \(n\)^th digit of the fractional part, find the value of the following expression.

\[d_1\times d_{10} \times d_{100} \times d_{1000} \times d_{10000} \times d_{100000}\times d_{1000000}\]

解决方案

每一个\(d_i\)都是一个独立的问题，可以先计算后再相乘。

可以发现，\(1\sim 9,10\sim 99,100\sim 999,\dots,10^{n-1}\sim 10^n-1,\dots\)，每一块都里面的数有相同的长度，而且，每一块的长度增长都是为\(1\)。

因此，计算每一个独立的\(d_i\)时，先找到第\(i\)位属于那一块，然后再判断第\(i\)位属于哪一个数，之后直接相乘即可。

代码

from itertools import count

que = [10 ** i for i in range(7)]


def cal(x: int):
    x -= 1
    for i in count(1, 1):
        l = 10 ** (i - 1)
        r = 10 ** i - 1
        if x >= (r - l + 1) * i:
            x -= (r - l + 1) * i
        else:
            d, pos = divmod(x, i)
            val = d + l
            ans = int(str(val)[pos])
            break
    return ans


ans = 1
for x in que:
    ans *= cal(x)
print(ans)