Đếm số chia hết cho M trong khoảng [A, B] C++

Cho ba số A, B, M. Đếm số nguyên trong khoảng [A, B] chia hết cho M.

Ví dụ minh họa

Ví dụ 1:

• Input: A = 11, B = 20, M = 5
• Output: 2
• Giải thích: 15, 20.

Ví dụ 2:

• Input: A = 20, B = 50, M = 11
• Output: 3
• Giải thích: 22, 33, 44.

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

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

int divisiblebyM(int a, int b, int m) {
    int count = 0;
    for (int i = a; i <= b; i++) {
        if (i % m == 0) count++;
    }
    return count;
}

int main() {
    int A = 3, B = 15, M = 4;
    cout << "So chia het cho " << M << " trong [" << A << "," << B << "]: "
         << divisiblebyM(A, B, M) << endl;
    return 0;
}

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

So chia het cho 4 trong [3,15]: 3

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

Số chia hết cho M trong [A, B] = ⌊B/M⌋ - ⌊(A-1)/M⌋

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

int divisiblebyMOptimized(int a, int b, int m) {
    if (m == 0) return 0; // Tránh chia cho 0
    return b / m - (a - 1) / m;
}

int main() {
    cout << divisiblebyMOptimized(11, 20, 5) << endl; // 2
    cout << divisiblebyMOptimized(20, 50, 11) << endl; // 3
    cout << divisiblebyMOptimized(3, 15, 4) << endl;  // 3
    return 0;
}

Độ phức tạp

Lưu ý

• Công thức hoạt động chính xác với số nguyên âm nếu xử lý đúng làm tròn (C++ làm tròn về 0).
• Với A, B lớn (≤ 10¹⁸), dùng long long.
• Kiểm tra M = 0 để tránh chia cho 0.