Đếm số nguyên m chữ số chia hết cho n trong C++

Cho hai số nguyên m và n. Đếm số lượng số nguyên có đúng m chữ số mà chia hết cho n.

Ví dụ minh họa

Ví dụ 1:

• Input: m = 2, n = 9
• Output: 10
• Giải thích: Các số 2 chữ số chia hết cho 9: 18, 27, 36, 45, 54, 63, 72, 81, 90, 99.

Ví dụ 2:

• Input: m = 3, n = 300
• Output: 3
• Giải thích: 300, 600, 900.

Xác định khoảng m chữ số

• Số nhỏ nhất m chữ số: 10^(m-1) (trừ m=1 thì là 0)
• Số lớn nhất m chữ số: 10^m - 1

Mã nguồn C++ (Duyệt tuần tự)

#include <bits/stdc++.h>
using namespace std;

int findCount(int n, int L, int R) {
    int count = 0;
    for (int i = L; i <= R; i++) {
        if (i % n == 0) count++;
    }
    return count;
}

int main() {
    int M = 2, N = 9;
    int num1 = 0; // Lớn nhất m-1 chữ số
    for (int i = 0; i < M - 1; i++) num1 = num1 * 10 + 9;
    int num2 = 0; // Lớn nhất m chữ số
    for (int i = 0; i < M; i++) num2 = num2 * 10 + 9;
    
    cout << "So " << M << " chu so chia het cho " << N << ": "
         << findCount(N, num1 + 1, num2);
    return 0;
}

Kết quả chạy chương trình

So 2 chu so chia het cho 9: 11

Tối ưu hóa O(1) - Công thức toán học

#include <bits/stdc++.h>
using namespace std;

long long countMDigitDivisible(int m, int n) {
    if (m <= 0 || n <= 0) return 0;
    
    long long lower = (m == 1) ? 0 : 1;
    for (int i = 1; i < m; i++) lower *= 10;  // 10^(m-1)
    long long upper = lower * 10 - 1;        // 10^m - 1
    
    // Số chia hết cho n trong [lower, upper]
    return upper / n - (lower - 1) / n;
}

int main() {
    cout << countMDigitDivisible(2, 9) << endl;  // 10
    cout << countMDigitDivisible(3, 300) << endl; // 3
    return 0;
}

Độ phức tạp

Lưu ý

• Dùng long long để tránh tràn số khi m lớn (m ≤ 18).
• Công thức: count = ⌊upper/n⌋ - ⌊(lower-1)/n⌋.