Project Euler 168

题目

Number Rotations

Consider the number $142857$. We can right-rotate this number by moving the last digit $(7)$ to the front of it, giving us $714285$.

It can be verified that $714285=5\times142857$.

This demonstrates an unusual property of $142857$: it is a divisor of its right-rotation.

Find the last $5$ digits of the sum of all integers $n, 10 < n < 10^{100}$, that have this property.

解决方案

令$N=100$。符合题意条件的数分成两部分：平凡的和非平凡的。

• 平凡的：这一部分数的所有数位都相等。如$11,222$等。它们的和为$\sum{i=2}^N\dfrac{10^i-1}{9}\times 45 = \sum{i=2}^N(10^i-1)\times 5$。

• 非平凡的：本人先通过暴力程序，找到了一部分解，在OEIS上进行搜索，结果为A034089。

找到COMMENT这一部分，发现如下信息：

Let p(q) denote the period of the fraction q; then sequence is generated by p(i / (10k-1)), k=2,3,4,5,6,7,8,9; k <= i <= 9 and the concatenations of those periods, e.g., p(7/39)=a(5) p(2/19)=a(17).

这说明，它是将每个分数$\dfrac{i}{10k-1}(2\le k\le i\le9)$的循环节不断用字符串进行拼接的形式构成的。如$\dfrac{7}{49}=\dfrac{1}{7}$，其循环节为$142857$，那么$142857142857$，$142857142857142857$等也是符合题意的数。

因此直接进行枚举。分数的循环节则用长除法产生。

代码

N = 100
ans = 0


def repeating_portion(x: int, y: int):
    s = ""
    vis = [0 for _ in range(y)]
    while True:
        x *= 10
        if vis[x % y]:
            break
        vis[x % y] = 1
        s += str(x // y)
        x %= y
    return s


for i in range(2, N + 1):
    ans += 5 * (10 ** i - 1)
for k in range(2, 9 + 1):
    for i in range(k, 9 + 1):
        s = repeating_portion(i, 10 * k - 1)
        t = s
        while len(t) <= N:
            ans += int(t)
            t += s
ans %= 10 ** 5
print(ans)