C++で階乗（n!）の各桁の合計を求める方法

問題の概要

ある整数 n が与えられたとき、n の階乗（n!）における各桁の数字の合計を求めることが課題です。例として n = 5 を考えてみましょう。この場合、n! = 120 となるので、1 + 2 + 0 = 3 が答えになります。

解法のアプローチ

階乗の値は n が大きくなるほど爆発的に増加するため、通常の整数型では表現できません。そこで、階乗の各桁を vector に1桁ずつ格納する手法を用います。これは筆算と同じ要領で、繰り上がりを処理しながら掛け算を繰り返す方法です。

1. 階乗の各桁を保存するための vector を作成し、初期値として 1 を入れておきます。
2. 1 から n までの各数値を順番に vector 全体へ掛けます。各桁ごとに「現在の桁 × 掛ける数 ＋ 繰り上がり」を計算し、10 で割った余りを新しい桁の値とします。
3. すべての掛け算が完了したら、vector 内の全要素を足し合わせて返します。

C++による実装例

#include<iostream>
#include<vector>
using namespace std;

// vector に格納された多倍長整数に x を掛ける関数
void vectorMultiply(vector<int> &v, int x) {
    int carry = 0, res;
    int size = v.size();
    for (int i = 0; i < size; i++) {
        res = carry + v[i] * x;
        v[i] = res % 10;
        carry = res / 10;
    }
    while (carry != 0) {
        v.push_back(carry % 10);
        carry /= 10;
    }
}

// n! の各桁の合計を求める関数
int digitSumOfFact(int n) {
    vector<int> v;
    v.push_back(1);
    for (int i = 1; i <= n; i++)
        vectorMultiply(v, i);
    int sum = 0;
    int size = v.size();
    for (int i = 0; i < size; i++)
        sum += v[i];
    return sum;
}

int main() {
    int n = 40;
    cout << n << "! の各桁の合計は: " << digitSumOfFact(n);
    return 0;
}

出力結果

40! の各桁の合計は: 189

コードのポイント

• vectorMultiply 関数： vector に格納された巨大な数に対して、下位の桁から順に x を掛け、繰り上がり（carry）を管理します。計算後に残った繰り上がりは、新たな桁として vector の末尾に追加されます。
• digitSumOfFact 関数： 初期値 1 から始めて、1 から n まで順番に掛けていくことで n! を構築し、その後すべての桁を合計して返します。

このプログラムでは n = 40 を計算しています。40! は 48 桁にも及ぶ巨大な数ですが、vector で各桁を管理することでオーバーフローを心配することなく、正確な桁の合計である 189 を求められます。同じ手法は 100! のようなさらに大きな階乗にもそのまま適用できます。