C++で整数Nの約数の中から最大の「良い数」を見つける方法

問題の概要

この問題では、ある整数 N が与えられ、その約数の中に含まれる最大の「良い数(good number)」を見つけることが求められます。

「良い数」とは?

「良い数」とは、どの桁の数字も、それより右側(下位の桁)にあるすべての数字の合計よりも大きい数のことです。

たとえば 732 は良い数です。「7 > 3 + 2」「3 > 2」という条件がすべて満たされているためです。

入出力例

入力 : N = 15
出力 : 15

解説: 15 の約数は 1, 3, 5, 15 の4つです。この中で最大の良い数は 15 となります。

解法のアプローチ

この問題へのシンプルな解法は、以下の手順で進めます。

1. 素因数分解によって、N のすべての素因数を求めます。
2. 求めたすべての素因数の積を計算します。
3. この積こそが、N の約数の中で条件を満たす最大の良い数となります。

素因数分解は、2 から √N まで順に試し割りを行うことで O(√N) の計算量で実行できるため、非常に効率的なアプローチです。

C++による実装例

上記の解法の動作を示すサンプルプログラムがこちらです。

#include <bits/stdc++.h>
using namespace std;
int findLargestGoodNumber(int n){
    vector<int> primeFactors;
    int x = n;
    for (int i = 2; i * i <= n; i++) {
        if (x % i == 0) {
            primeFactors.push_back(i);
            while (x % i == 0)
                x /= i;
        }
    }
    if (x > 1)
        primeFactors.push_back(x);
    int goodNumber = 1;
    for (int i = 0; i < primeFactors.size(); i++)
        goodNumber = goodNumber * primeFactors[i];
    return goodNumber;
}
int main(){
    int n = 28;
    cout<<"The largest good Number in divisor of "<<n<<" is "<<findLargestGoodNumber(n);
   return 0;
}

実行結果

The largest good Number in divisor of 28 is 14

このプログラムでは N = 28 を処理しています。28 を素因数分解すると 28 = 2 × 2 × 7 となるため、異なる素因数は 2 と 7 です。その積である 2 × 7 = 14 が答えとなります。

まとめ

与えられた整数 N の約数の中から最大の良い数を見つけるには、N を素因数分解し、すべての異なる素因数を掛け合わせるだけでよいことが分かりました。試し割り法を用いれば O(√N) で求められるため、大きな N に対しても高速に動作する実用的な手法です。