Thêm N chữ số vào A chia hết cho B sau mỗi lần (Phiên bản 2)

Tạo số A bằng cách thêm N chữ số, sao cho sau mỗi lần thêm, số mới chia hết cho B. Nếu không thể, trả về -1.

Ví dụ

Input: A=8, B=7, N=4
Output: 84000
Giải thích: 84 chia hết 7, thêm 000 → 84000

Input: A=10, B=11, N=5
Output: Unable to get this type of number

Thuật toán

1. Thử thêm chữ số 0-9 vào A: temp = A*10 + d. Nếu temp % B == 0 → chọn d.
2. Nếu không tìm được d nào → trả về -1.
3. Sau khi có số chia hết, thêm (N-1) chữ số 0 (vì nếu X|A thì X|A*10^k).

Code ví dụ

#include <iostream>
using namespace std;

long long addNDigits(long long a, int b, int n) {
    long long original = a;
    
    // Tìm chữ số đầu tiên
    for(int d = 0; d <= 9; d++) {
        long long temp = a * 10 + d;
        if (temp % b == 0) {
            a = temp;
            break;
        }
    }
    
    // Không tìm thấy
    if (a == original) return -1;
    
    // Thêm (n-1) chữ số 0
    for(int i = 0; i < n - 1; i++)
        a *= 10;
    
    return a;
}

int main() {
    long long a; int b, n;
    cout << "Nhap A, B, N: ";
    cin >> a >> b >> n;
    
    long long res = addNDigits(a, b, n);
    if (res == -1)
        cout << "Khong the tao so thoa man";
    else
        cout << "Ket qua: " << res;
    return 0;
}

Kết quả

Nhap A, B, N: 8 7 4
Ket qua: 84000

Nhap A, B, N: 10 11 5
Khong the tao so thoa man

Độ phức tạp

• Thời gian: O(10 + N) = O(N) - rất nhanh.
• Không gian: O(1).

Lưu ý kiểu dữ liệu

• Dùng long long cho A (có thể lên đến 10¹⁸).
• Nếu N rất lớn (kết quả > 10¹⁸), cần big integer hoặc xuất dưới dạng string.

Phiên bản xuất string (không giới hạn kích thước)

string addNDigitsString(string a, int b, int n) {
    // Tìm chữ số đầu
    for(char d = '0'; d <= '9'; d++) {
        string temp = a + d;
        // Tính mod của số lớn
        int mod = 0;
        for(char c : temp) mod = (mod * 10 + c - '0') % b;
        if (mod == 0) {
            a = temp;
            break;
        }
    }
    if (a.length() == a.find_last_not_of('0') + 1 && a.back() != '0') // logic check...
    // Đơn giản: thêm n-1 '0'
    a += string(n-1, '0');
    return a;
}