Chương trình C++ tìm số K chữ số nhỏ nhất chia hết cho X (Phiên bản 2)

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

Thuật toán

1. Số K chữ số nhỏ nhất: min = 10^(K-1) (10, 100, 1000...).
2. Nếu min % X == 0 → trả về min.
3. Ngược lại: (min + X) - ((min + X) % X).

Ví dụ

K=5, X=29. min = 10000. 10000 % 29 = 14. (10000+29) % 29 = 14. Kết quả = 10029 - 14 = 10015.

Kiểm tra: 10015 / 29 = 345.34... SAI! Công thức gốc có lỗi.

Công thức đúng

Bội số của X lớn nhất ≥ min: min + (X - min % X) % X

Hoặc đơn giản: ((min + X - 1) / X) * X (làm tròn lên bội số gần nhất).

Code sửa lỗi

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

long long minKDigit(int k, int x) {
    long long minVal = 1;
    for(int i = 1; i < k; i++) minVal *= 10; // 10^(k-1)
    
    if (minVal % x == 0) return minVal;
    
    // Làm tròn lên bội số của x gần nhất
    return ((minVal + x - 1) / x) * x;
}

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

Kết quả

Nhap K va X: 5 29
Ket qua: 10005

Nhap K va X: 6 87
Ket qua: 100050

Kiểm tra

10005 / 29 = 345 ✓
100050 / 87 = 1150 ✓

Lưu ý

• Code gốc có công thức sai: (min+X) - ((min+X)%X) không luôn đúng.
• Dùng long long tránh tràn (K ≤ 18).
• K > 18 cần big integer.