C++でN階乗の合計の下2桁を求める方法

本記事では、1!からN!までの階乗の合計について、その下2桁(一の位と十の位)を求める方法を解説します。例えば N = 4 の場合、1! + 2! + 3! + 4! = 33 となるため、一の位は「3」、十の位は「3」であり、結果は「33」となります。

この問題には重要な性質があります。N が 5 より大きい場合、その階乗の一の位は必ず 0 になるため、6! 以降の項は一の位に一切影響を与えません。同様に、N が 10 以上になると十の位も 0 のまま変化しなくなります。したがって、N = 10 以上では結果は常に「13」で固定されます。実際に N = 1 から 10 までの階乗の値を表に整理すると、この法則がよく分かります。

解法のアプローチ

上記の性質を利用すると、この問題は次の手順で効率的に解くことができます。

• n < 10 の場合:(1! + 2! + … + n!) を直接計算し、100 で割った余りを求める
• n ≥ 10 の場合:(1! + 2! + … + 10!) mod 100 = 13 となるため、答えは常に 13 を返す

この方法により、n ≤ 10 のときは O(n)、それ以外は O(1) という非常に高速な計算が可能です。

C++による実装例

#include<iostream>
#include<cmath>
using namespace std;
int getTenAndUnitPlace(long long N) {
    if (N <= 10) {
        long long ans = 0, factorial = 1;
        for (int i = 1; i <= N; i++) {
            factorial = factorial * i;
            ans += factorial;
        }
        return ans % 100;
    }
    return 13;
}
int main() {
    for(long long i = 1; i<15; i++){
        cout << "N = " <<i<<" のときの階乗の合計の下2桁: " <<getTenAndUnitPlace(i) << endl;
    }
}

実行結果

N = 1 のときの階乗の合計の下2桁: 1
N = 2 のときの階乗の合計の下2桁: 3
N = 3 のときの階乗の合計の下2桁: 9
N = 4 のときの階乗の合計の下2桁: 33
N = 5 のときの階乗の合計の下2桁: 53
N = 6 のときの階乗の合計の下2桁: 73
N = 7 のときの階乗の合計の下2桁: 13
N = 8 のときの階乗の合計の下2桁: 33
N = 9 のときの階乗の合計の下2桁: 13
N = 10 のときの階乗の合計の下2桁: 13
N = 11 のときの階乗の合計の下2桁: 13
N = 12 のときの階乗の合計の下2桁: 13
N = 13 のときの階乗の合計の下2桁: 13
N = 14 のときの階乗の合計の下2桁: 13

実行結果からも確認できるように、N が 7 以降は答えが「13」で固定されており、N ≥ 10 で常に一定となる理論どおりの動作をしています。大きな N に対しても定数時間で答えを返せる点が、このアルゴリズムの大きな利点です。