C++でN階乗の合計の下一桁（一の位）を求める方法

この記事では、C++を使って「1! + 2! + ... + N!」という階乗の合計の下一桁（一の位）を求める方法を解説します。例えばN = 3の場合、1! + 2! + 3! = 9 となるため答えは9、N = 4の場合は 1! + 2! + 3! + 4! = 33 となり、下一桁は3になります。

階乗の下一桁の重要な性質

この問題を解く鍵となるのは、5以上の数の階乗の下一桁が必ず0になるという性質です。5! = 120、6! = 720、7! = 5040 のように、5!以降はすべて一の位が0になります。これは、5以上の階乗には必ず因数2と5のペアが含まれ、10の倍数になるためです。

したがって、Nが5以上であっても、それらの階乗は合計の下一桁に一切影響を与えません。結果として、N = 4以降は下一桁が常に3になります。

下一桁の対応表

C++での実装例

この性質を利用すれば、Nがどれほど大きな値でも、あらかじめ用意した表を参照するだけで下一桁を即座に求められます。以下がそのC++コードです。

#include<iostream>
#include<cmath>
using namespace std;
double getUnitPlace(int n) {
    int placeVal[5] = {-1, 1, 3, 9, 3};
    if(n > 4){
        n = 4;
    }
    return placeVal[n];
}
int main() {
    for(int i = 1; i<10; i++){
        cout << "N = " << i << " のときの階乗の合計の下一桁: " << getUnitPlace(i) << endl;
    }
}

実行結果

N = 1 のときの階乗の合計の下一桁: 1
N = 2 のときの階乗の合計の下一桁: 3
N = 3 のときの階乗の合計の下一桁: 9
N = 4 のときの階乗の合計の下一桁: 3
N = 5 のときの階乗の合計の下一桁: 3
N = 6 のときの階乗の合計の下一桁: 3
N = 7 のときの階乗の合計の下一桁: 3
N = 8 のときの階乗の合計の下一桁: 3
N = 9 のときの階乗の合計の下一桁: 3

コードの解説

getUnitPlace関数では、配列placeValにN = 0〜4に対応する下一桁の値 {-1, 1, 3, 9, 3} を格納しています。Nが4より大きい場合は下一桁が常に3であるため、nを4に制限しています。この実装により、Nの値に関わらずO(1)の定数時間で答えを求めることができ、大きなNに対しても階乗を実際に計算する必要がありません。