Project Euler Problem 26

1/d が最も長い循環部分を持つような d (1 < d < 1000) を求めよ。

これは、普通に割り算の筆算と同じ事をやればいいな。余りをsetに持つようにして、同じ余りが出てきた時点でループと見なして検出すればよい。

ただし、1周目はループの長さはわからない（最初にゴミが入っている可能性がある）ので、2周目を検出しなくてはならないのが面倒なところだけど。

この余分な手順は、余りをすべて数列として持って厳密に数列からループ検出をすれば必要ない。だけど、そうすると結構時間がかかりそうな気がするし、かえって複雑になる気がするので却下。

下のプログラムは、「ループ長 d」という順番で表示するようになっている。sort に渡せば答えが出る。

#!/usr/bin/python

import sys

def calc(d):
    a = 1

    mod_set = set()

    while True:
        a *= 10

        if (a % d) in mod_set:
            break
        else:
            mod_set.add(a % d)
        a %= d

    mod_set = set()

    length = 0
    while True:
        a *= 10

        if (a % d) in mod_set:
            break
        else:
            mod_set.add(a % d)
            length += 1

        a %= d

    return length

for i in range(2, 1000):
    print "%04d, %d" % (calc(i), i)