【C++】Dで割り切れるN桁の数を見つけるアルゴリズム

2つの整数 N と D が与えられたとき、D で割り切れる N 桁の数を見つける問題を考えます。例えば、N = 3、D = 5 の場合、答えは 500 になります。一見難しそうに思えるこの問題ですが、実はとてもシンプルな発想で解決できます。

解法のアイデア

基本となる考え方は、「D を先頭に置き、その後ろに 0 を付け足して N 桁にする」というものです。D の桁数を m とすると、D の末尾に (N − m) 個の 0 を連結した数は、全体でちょうど N 桁となり、必ず D で割り切れます。これは、作成される数が D × 10^(N−m) に相当し、10 のべき乗を掛けても D で割り切れるという性質が保たれるためです。

ただし、例外がひとつあります。D が 10 以上で、かつ N が 1 の場合です。このとき、1 桁の数で D を割り切ることはできないため、条件を満たす数は存在しません。プログラムではこのケースを検出し、「数が見つからない」旨を返すようにします。

アルゴリズムの手順

1. D を文字列に変換し、その桁数 m を取得する。
2. D ≥ 10 かつ N = 1 の場合は解が存在しないため、エラーメッセージを返す。
3. それ以外の場合は、D の文字列の末尾に (N − m) 個の '0' を追加する。
4. 完成した文字列を結果として返す。

C++での実装例

#include<iostream>
using namespace std;

// D で割り切れる N 桁の数を文字列として生成する関数
string nDigitDivByD(int n, int d) {
    string ans = "";
    if (d < 10) { // D が 1 桁の場合
        ans += to_string(d);
        for (int i = 1; i < n; i++)
            ans += "0";
    } else { // D が 2 桁以上の場合
        if (n == 1)
            return "Cannot find any number"; // 解が存在しない
        else {
            string temp = to_string(d); // D の桁数を取得
            ans += to_string(d);
            for (int i = 0; i < n - temp.length(); i++)
                ans += "0";
        }
    }
    return ans;
}

int main() {
    int n = 5, d = 15;
    cout << nDigitDivByD(n, d);
}

出力

15000

この例では N = 5、D = 15 が与えられているため、15 の末尾に 3 個の 0 を付けた 15000 が出力されます。15000 は確かに 5 桁であり、15 で割り切れる数になっています。

計算量について

このアルゴリズムは文字列の構築が中心の処理となるため、時間計算量は O(N)、使用するメモリも O(N) で済みます。桁数が大きくなっても線形時間で処理できるため、非常に効率的な解法と言えます。