C++で（1^n + 2^n + 3^n + 4^n）mod 5を効率的に求める方法

このチュートリアルでは、次の問題を解説します。

整数 n が与えられたとき、(1ⁿ+2ⁿ+3ⁿ+4ⁿ) % 5 の値を求める必要があります。

問題点：直接計算できない理由

n が大きくなると、(1ⁿ+2ⁿ+3ⁿ+4ⁿ) の値は爆発的に増大し、long long 型のような整数型にすら収まらなくなります。そのため、実際にべき乗を計算せずに済む別のアプローチが必要になります。

規則性の発見

まず、この式を n = 1, 2, 3, ..., 9 について実際に計算してみると、それぞれ次のような値が得られます。

10, 30, 100, 354, 1300, 4890, 18700, 72354, 282340

これらの結果の末尾の数字（下一桁）を注意深く観察してください。実は、4つごとに末尾の数字が同じパターンで繰り返されることが分かります。これがこの式の持つ周期性です。

つまり、式を実際に計算しなくても、次のように結論できます。

n % 4 == 0 の場合：(1ⁿ+2ⁿ+3ⁿ+4ⁿ) % 5 は 4
上記以外の場合：(1ⁿ+2ⁿ+3ⁿ+4ⁿ) % 5 は 0

なぜこの法則が成り立つのか

フェルマーの小定理より、5と互いに素な任意の整数 a に対して a⁴ ≡ 1 (mod 5) が成り立ちます。したがって、n が4の倍数のとき、各項は mod 5 ですべて 1 となり、合計は 4 になります。一方、n が4の倍数でない場合も、指数を mod 4 で考えることで、各項の和が必ず5の倍数になることを確認できます。

実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int findSequenceMod5(int n) {
    // nが4の倍数なら4、そうでなければ0を返す
    return (n % 4) ? 0 : 4;
}

int main() {
    int n = 343;
    cout << findSequenceMod5(n) << endl;
    return 0;
}

出力結果

上記のコードを実行すると、次の結果が出力されます。

0

n = 343 の場合、343 % 4 = 3 となるため、結果は 0 になります。このアルゴリズムの計算量は O(1) であり、n がどれほど大きくても即座に答えを求められます。

まとめ

このように、一見巨大な数を扱う問題でも、数列の周期性や規則性を見抜くことで、効率的かつオーバーフローの心配なく解くことができます。本チュートリアルについて質問がある場合は、コメント欄でお知らせください。