C++で与えられた数がその桁の階乗の合計を割り切るかどうかを判定する方法

問題の概要

ある整数が与えられたとき、その数自身が「各桁の階乗の合計」を割り切るかどうかを判定する方法を解説します。

例として、数が19の場合を考えてみましょう。各桁の階乗の合計は次のように計算されます。

(1! + 9!) = 1 + 362880 = 362881

362881 ÷ 19 = 19099 となり余りは0なので、19は各桁の階乗の合計を割り切ることができる数です。

解決のアプローチ

この問題は、以下の手順で解くことができます。

1. 元の数を一時変数に保存しておく
2. 数の各桁を取り出し、それぞれの階乗を計算して合計する
3. 合計が元の数で割り切れるかどうかを判定し、結果を返す

C++による実装例

#include <iostream>
using namespace std;
int factorial(int n){
    if(n == 1 || n == 0)
        return 1;
    return factorial(n - 1) * n;
}
bool isDigitsFactDivByNumber(int num){
    int temp = num;
    int sum = 0;
    while(num){
        int digit = num % 10;
        sum += factorial(digit);
        num /= 10;
    }
    if(sum % temp == 0){
        return true;
    }
    return false;
}
int main() {
    int number = 19;
    if (isDigitsFactDivByNumber(number))
        cout << "はい、この数は各桁の階乗の合計を割り切ることができます。";
    else
        cout << "いいえ、この数は各桁の階乗の合計を割り切ることができません。";
}

コードの解説

factorial関数は、再帰呼び出しを用いて階乗を計算します。0と1の階乗はどちらも1と定義されているため、これらを再帰の終了条件(基底条件)としています。

isDigitsFactDivByNumber関数では、まず引数の値を一時変数tempに保存します。これは、whileループの処理でnumの値が変化してしまうため、最終的な判定時に元の値が必要になるからです。ループ内では、num % 10によって最下位の桁を1桁ずつ取り出し、その階乗を合計sumに加算します。その後、num /= 10で数を1桁右にずらしていきます。

すべての桁の処理が完了したら、剰余演算子%を使って合計が元の数で割り切れるかを判定します。余りが0であればtrueを、そうでなければfalseを返します。

実行結果

はい、この数は各桁の階乗の合計を割り切ることができます。

計算量について

このアルゴリズムの時間計算量はO(d)です。ここでdは入力された数の桁数を表します。各桁の階乗計算は0!から9!までの範囲に収まるため、実質的に定数時間で処理できます。また、再帰の深さも最大9程度に抑えられるため、空間計算量はO(1)とみなせます。

まとめ

桁の抽出・階乗計算・剰余判定というシンプルな処理を組み合わせることで、与えられた数がその桁の階乗の合計を割り切るかどうかを効率的に判定できます。なお、145のように「各桁の階乗の合計が元の数自身と等しくなる数(ファクトリオン)」も存在し、このような数は当然ながら自分自身で割り切ることができます。