C++で1/nの小数展開における循環節の長さを求める方法

循環節の長さとは

ある数 n が与えられたとき、1/n の小数展開における循環節（繰り返し部分）の長さを求めることを考えます。

例えば、n = 7 の場合を見てみましょう。

1/7 = 0.142857142857…

太字で示した「142857」の部分が無限に繰り返されています。この場合、循環節の長さは 6 となります。

アルゴリズムの考え方

割り算の筆算を手で行うことを思い出してください。各ステップで現れる「余り」に注目すると、次のことが分かります。

• 数 n で割ったときの余りは、0 から n-1 までの最大 n 種類しか存在しません。
• しかし、循環節は必ずしも最初の余りから始まるとは限りません。小数点以下の最初の数桁は循環しない部分（有限小数部分）である場合があるためです。

そこで、確実に循環節に含まれる余りを取得するために、次の手順で計算を行います。

1. 余りを 1 で初期化し、(n+1) 回「余り = (10 × 余り) % n」を繰り返します。鳩の巣原理により、(n+1) 回目までには必ず循環節内の余りに到達します。
2. その時点の余りの値を記録します。
3. 同じ余りが再び現れるまで同じ計算を繰り返し、その繰り返し回数を数えます。
4. (n+1) 番目の余りから次に同じ余りが現れるまでの距離が、求める循環節の長さとなります。

C++での実装例

#include<iostream>
using namespace std;

int periodLength(int n) {
    int remainder = 1;
    int length = 0;

    // (n+1) 回計算を進め、確実に循環節内の余りに到達させる
    for (int i = 1; i <= n + 1; i++)
        remainder = (10 * remainder) % n;

    int d = remainder;  // 循環節内の余りを記録

    // 同じ余りが再び現れるまで繰り返す
    do {
        remainder = (10 * remainder) % n;
        length++;
    } while (remainder != d);

    return length;
}

int main() {
    int n = 7;
    cout << "Period length of 1/" << n << " is: " << periodLength(n) << endl;
    return 0;
}

実行結果

Period length of 1/7 is: 6

コードの解説

periodLength 関数は、筆算と同じ要領で余りを更新していきます。各ステップで余りに 10 を掛けて n で割った余りを求める操作は、「次の桁を取り出して余りを更新する」ことに相当します。

最初の for ループで (n+1) 回計算を進めているのは、循環が始まる前の非循環部分をスキップするためです。その後の do-while ループで、記録した余り d が再び現れるまでのステップ数を数えることで、循環節の長さが得られます。

他の入力例

• n = 3 の場合：1/3 = 0.333… なので、循環節の長さは 1
• n = 28 の場合：1/28 = 0.03571428571428… なので、循環節の長さは 6
• n = 2 の場合：1/2 = 0.5 と割り切れるため、循環節は存在せず長さは 0

このアルゴリズムの計算量は O(n) であり、余りの種類が高々 n 個であることから、必ずその範囲内で循環が検出されることが保証されています。