Project Euler - Problem 358

Cyclic numbers

n 桁の巡回数はとても興味深い特性を持っている :
1,2,3,4, ... n で乗算すると, すべての積が同じ桁数になり, 同じ順番で現れ, しかも輪状に回転している！

最小の巡回数は6桁の数 142857 である :

142857 × 1 = 142857
142857 × 2 = 285714
142857 × 3 = 428571
142857 × 4 = 571428
142857 × 5 = 714285
142857 × 6 = 857142

次の巡回数は16桁の数 0588235294117647 である :

0588235294117647 × 1 = 0588235294117647
0588235294117647 × 2 = 1176470588235294
0588235294117647 × 3 = 1764705882352941

...
0588235294117647 × 16 = 9411764705882352

巡回数について留意すべきこととして, 先行ゼロ(数の先頭につくゼロ)が重要である.

最左からの11桁が 00000000137, 最右からの5桁が 56789 となる巡回数が唯一存在する. (すなわち, 内部の桁が明かされていない 00000000137...56789 という形をもつ)
この数のすべての桁の合計を求めよ.

(日本語訳より)

個人的に楽しい問題だったのでチラ見の人は一度解いてみるといいと思う

巡回数，特に 142857 なんかは子供向けおもしろ数学辞典なんかにも載ってる有名な話だったりする．

1 / p (p はある条件を満たす素数) の循環小数表記と深い関わりがあるそうですが，Wikipedia なんかを見ると色々書いてある．

例えば

1 / 7 = 0.14285714285714285714285714285714...
2 / 7 = 0.28571428571428571428571428571429...
...

1 / 17 = 0.05882352941176470588235294117647...
2 / 17 = 0.11764705882352941176470588235294...
...

1 / 19 = 0.05263157894736842105263157894737...
2 / 19 = 0.10526315789473684210526315789474...
...

みたいな．

それはそれとして問題について

巡回数は巡回小数 1 / p をあれこれして得られるものであるということを念頭に置くと，
最左からの 11 桁が 00000000137 ということで，ある程度調べるべき範囲は限定される．つまり，

0.00000000137 ≦ 1 / p < 0.00000000138

より，

724637682 < p ≦ 729927007

これで解候補がだいたい 5,000,000 くらいになった．

次に最右の 5 桁が 56789 ということですが，約 5,000,000 ケースについて逐一調べていると死ぬのである程度候補を絞る必要がある．

使うのは巡回数の性質で

142857 * 7 = 999,999
0588235294117647 * 17 = 9,999,999,999,999,999
052631578947368421 * 19 = 999,999,999,999,999,999

のように巡回数に対応する分数 1 / p の分母 p を巡回数に掛けると 9 が p - 1 桁並ぶ．

よって最右の 5 桁に解候補 p を掛けた場合，末尾の 5 桁は 99999 となることがわかる．
これによって解候補は約 1 / 100000 の 53 個になる(！)

で，さらに候補を絞ることができて，

巡回数となる分数の分母は素数である．
ただし p − 1 桁未満の 9 の列で割り切れると巡回数とはならない．(Wikipedia)

ということで，素数以外を弾くと解候補は 3 つに絞られる．

解候補に対して AC 貰うまで解答を投げるクソプレイをしないために 1 つに絞る必要がある．

残り使えそうな性質は

巡回数となる分数の分母は素数である．
ただし p − 1 桁未満の 9 の列で割り切れると巡回数とはならない．(Wikipedia)

ですが，9999999999999999...99999 を p が割り切るということは

10^d ≡ 1 (mod p)　(d < p - 1)

にほかならない．このような d が見つかった時点で解候補から除外すればよい．

これを使えばめでたく解候補が 1 つに絞られるので，あとは頑張って 1 / p の小数点以下 p - 1 桁以下をすべて足し合わせてやればよい．

bool is_prime(lint n)
{
    lint i;
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;

    for (i = 3; i * i <= n; i += 2) {
        if (n % i == 0)  return false;
    }
    return true;
}

// 1 / n (n >= 2) の小数点 d 桁までの数字の和を求める
lint digit_sum(lint n, lint d) {
    lint ret = 0;

    lint p = 10;
    while (d > 0) {
        lint q = p / n;
        p %= n;
        p *= 10;
        ret += q;
        d--;
    }
    return ret;
}

// 10^d - 1 (2 <= d < p - 1) を 素数 p が割り切るかどうか
bool is_divisor(lint p) {
    lint x = 10;
    for (lint d = 2; d < p - 1; d++) {
        x *= 10;
        x %= p;
        if (x == 1) return true;
    }
    return false;
}

int main() {

    clock_t start, end;
    start = clock();
    
    const lint MIN = 724637682;
    const lint MAX = 729927007;
    
    vector<lint> vec;
    for (lint x = MIN; x <= MAX; x++) {
        if (x * 56789 % 100000 == 99999 && is_prime(x)) vec.push_back(x);
    }
    
    for (int i = 0; i < vec.size(); i++) {
        lint p = vec[i];

        if (is_divisor(p)) continue;
        cout << digit_sum(p, p - 1) << endl;
    }

    end = clock();
    printf("%f sec.\n", double(end - start) / CLOCKS_PER_SEC);
    return 0;
}