Chương trình C++ tìm số K chữ số lớn nhất chia hết cho X

Tìm số K chữ số lớn nhất chia hết cho X.

Thuật toán

1. Số K chữ số lớn nhất: max = 10^K - 1 (ví dụ: 99, 999, 9999...).
2. Nếu max chia hết cho X → trả về max.
3. Ngược lại: max - (max % X) (bội số của X nhỏ nhất ≤ max).

Ví dụ

K=5, X=29. max = 99999. 99999 % 29 = 7. Kết quả = 99999 - 7 = 99992. Kiểm tra: 99992 / 29 = 3448 ✓

Code ví dụ

#include <iostream>
#include <cmath>
using namespace std;

long maxKDigit(int k, int x) {
    long max = pow(10, k) - 1;  // 10^k - 1
    if (max % x == 0) return max;
    return max - (max % x);
}

int main() {
    int k, x;
    cout << "Nhap K (so chu so) va X (boi so): ";
    cin >> k >> x;
    cout << "Ket qua: " << maxKDigit(k, x);
    return 0;
}

Kết quả mẫu

Nhap K va X: 5 29
Ket qua: 99992

Nhap K va X: 6 87
Ket qua: 999978

Lưu ý

• pow(10, k) trả về double, có thể sai số làm tròn khi k lớn. Nên tự viết lũy thừa nguyên hoặc dùng long long.
• Với K lớn (K > 18), cần dùng big integer (boost::multiprecision::cpp_int).

Phiên bản an toàn hơn (tránh pow)

long long maxKDigitSafe(int k, int x) {
    long long max = 1;
    for (int i = 0; i < k; i++) max *= 10;
    max -= 1; // 10^k - 1
    return max - (max % x);
}

Độ phức tạp

• Thời gian: O(K) hoặc O(1) tùy cách tính 10^K.
• Không gian: O(1).