Đếm ước số của A hoặc B trong khoảng [L, R] C++

Cho L, R, A, B. Đếm số nguyên trong [L, R] chia hết cho A HOẶC B (hoặc cả hai).

Ví dụ minh họa

Ví dụ 1:

• Input: L = 10, R = 15, A = 4, B = 3
• Output: 2
• Giải thích: 12 chia hết cho cả 3 và 4. 15 chia hết cho 3. Tổng 2 số.

Ví dụ 2:

• Input: L = 20, R = 30, A = 17, B = 19
• Output: 0

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

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

int countDivisors(int l, int r, int a, int b) {
    int count = 0;
    for (int i = l; i <= r; i++) {
        if (i % a == 0 || i % b == 0) count++;
    }
    return count;
}

int main() {
    int L = 5, R = 15, A = 2, B = 5;
    cout << "Tong uoc so cua A hoac B: " << countDivisors(L, R, A, B);
    return 0;
}

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

Tong uoc so cua A hoac B: 7

Tối ưu hóa O(1) - Nguyên lý bao hàm loại trừ

Số chia hết cho A hoặc B = (chia hết cho A) + (chia hết cho B) - (chia hết cho cả A và B).

Chia hết cho cả A và B ⇔ chia hết cho LCM(A, B).

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

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

long long countDivisible(long long l, long long r, long long d) {
    if (d == 0) return 0;
    return r / d - (l - 1) / d;
}

long long countDivisorsOptimized(long long l, long long r, long long a, long long b) {
    long long lcm_ab = lcm(a, b);
    return countDivisible(l, r, a) + countDivisible(l, r, b) - countDivisible(l, r, lcm_ab);
}

int main() {
    cout << countDivisorsOptimized(10, 15, 4, 3) << endl; // 2
    cout << countDivisorsOptimized(5, 15, 2, 5) << endl;  // 7
    return 0;
}

Độ phức tạp

Lưu ý

• Dùng long long cho A, B, L, R lớn (≤ 10¹⁸).
• Tính LCM cẩn thận tràn số: a / gcd(a,b) * b thay vì a * b / gcd.