毎回Bで割り切れるようにAにN桁を追加するアルゴリズム

問題概要

整数 a、b、n が与えられます。a の末尾に1桁ずつ数字を追加していき、毎回の追加後にその数が b で割り切れるようにすることが求められます。

• 数字を1桁追加した直後、a が b で割り切れるようにします。

• この操作を n 回繰り返したとき、あり得る最小の a の値を出力します。

• 条件を満たすことができない場合は fail を出力します。

なお、1桁追加するごとに必ず割り切れているかどうかを確認する必要があります。

入出力例

入力：

a=5 b=4 n=4

出力：

52000

解説

まず、追加する最初の1桁として 0〜9 の数字を順番に試します。どの数字を追加しても a が b で割り切れない場合、答えは -1 となり、これは n 桁を追加しても a が決して b で割り切れないことを意味します。

一方、条件を満たす数字が存在する場合は、その中で最も小さい数字を採用し、残りの (n-1) 桁にはすべて 0 を追加します。ある数が b で割り切れるならば、a×10、a×100…も同様に b で割り切れるためです。この貪欲な戦略によって、常に最小の答えが得られます。

C++ 実装例

#include <iostream>
using namespace std;

int main() {
    int a = 5, b = 4, n = 4;
    int num = a;

    // 追加する最初の1桁を0〜9の中から探索
    for (int i = 0; i <= 9; i++) {
        int temp = a * 10 + i;
        if (temp % b == 0) {
            a = temp;
            break;
        }
    }

    // 条件を満たす桁が見つからなかった場合
    if (num == a) {
        a = -1;
    }

    // 残りの(n-1)桁はすべて0を追加
    for (int j = 0; j < n - 1; j++) {
        a *= 10;
    }

    if (a > -1) {
        cout << a;
    } else {
        cout << \"fail\";
    }
    return 0;
}

計算量と注意点

最初の1桁の探索は最大でも10回の試行で済むため、全体の計算量は O(1) と非常に効率的です。ただし、桁を追加するたびに a は急速に大きくなるため、int 型ではオーバーフローする恐れがあります。大きな入力に対応する場合は、文字列として処理するか、long long 型や多倍長整数を利用することをおすすめします。