C++でAにN桁を追加し、毎回の追加後にBで割り切れる数を生成する方法

問題の概要

本記事では、数値AにN桁を追加して新しい数値を作成する方法を解説します。ただし、各段階で桁を追加した直後に、その数値が別の数値Bで割り切れるという条件を満たす必要があります。

具体例として、「8」から始まる5桁の数を作り、4桁を追加しながら7での割り切りを確認するケースを考えてみましょう。最初に8に4を付け足すと「84」となり、これは7で割り切れます。その後は0を追加しても「840」「8400」「84000」と、いずれも7で割り切れたままです。もし条件を満たす数値が生成できない場合は、-1を返します。

アルゴリズムの考え方

基本的な戦略はシンプルです。各ステップで0から9までの数字を順番に試し、その数字を末尾に付けてもBで割り切れるものを探します。一度割り切れる数値が完成すれば、残りの桁にはすべて0を追加できます。なぜなら、Bで割り切れる数値を10倍しても、依然としてBで割り切れるからです。

addNDigits(a, b, n)

begin
    num := a
    for all number x from 0 to 9, do
        temp := a * 10 + x
        if temp mod b is 0, then
            a := temp
            break
        end if
    done
    if num = a, then
        return -1
    end if
    add remaining 0's with a
    return a.
end

C++による実装例

#include<iostream>
using namespace std;
int add_n_digits(int a, int b, int n) {
    int num = a;
    for (int i = 0; i <= 9; i++) { //すべての数字(0〜9)を追加して試す
        int tmp = a * 10 + i;
        if (tmp % b == 0) {
            a = tmp; //追加後にaを更新
            break;
        }
    }
    if (num == a) //1桁も追加できなかった場合は-1を返す
        return -1;
    for (int j = 0; j < n - 1; j++) //割り切れる数が見つかった後は0を追加
        a *= 10;
    return a;
}
main() {
    int a, b, n;
    cout << "Enter A, B and N: ";
    cin >> a >> b >> n;
    int res = add_n_digits(a, b, n);
    if(res == -1) {
        cout << "Unable to get this type of number";
    } else {
        cout << "Result is " << res;
    }
}

出力例

Enter A, B and N: 8 7 4
Result is 84000

入力「A=8, B=7, N=4」の場合、8に4を追加して84（7で割り切れる）となり、その後0を3つ追加して84000が得られます。

Enter A, B and N: 10 11 5
Unable to get this type of number

一方、入力「A=10, B=11, N=5」の場合、10にどの数字を追加しても11で割り切れる数にならないため、-1が返され「生成できない」と表示されます。

計算量と注意点

最初の桁の探索では最大10回の剰余チェックを行うだけなのでO(1)、その後は残りのN-1桁に対して10倍の操作を繰り返すため、全体の時間計算量はO(N)と非常に効率的です。

なお、桁数Nが大きくなるとint型ではオーバーフローする可能性があるため、実際の応用ではlong long型や多倍長整数、あるいは文字列ベースの実装を検討してください。また、標準C++ではmain関数にはint型の戻り値を指定することが推奨されます。