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)