Hiểu bài toán

Cho Q truy vấn. Mỗi truy vấn gồm 4 số nguyên dương l, r, a, b. Nhiệm vụ của bạn là đếm số lượng số nguyên x trong khoảng [l, r] sao cho x chia hết cho a hoặc x chia hết cho b.

Các cách tiếp cận

Cách Brute Force

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

int main() {
  freopen("countdiv.INP", "r", stdin);
  freopen("countdiv.OUT", "w", stdout);
   int q ; cin>> q ; 
   while(q--){ 
      ll r , l , a , b ; cin >> r >> l >> a >> b ; 
      ll ans = 0 ; 
      for(int i = r ; i <= l ; i++){
         if (( i % a == 0 )  || ( i%  b == 0)){
              ans++; 
         }
      }
      cout << ans  << endl ;
    }
}

• Time Complexity: O(Q * (r - l))
• Space Complexity: O(1)

Hàm main trong 2 solution đầu tiên sử dụng vòng lặp từ r đến l để kiểm tra từng số. Nếu số đó chia hết cho a hoặc b, ta tăng biến đếm ans. Cách này đơn giản nhưng rất chậm, chỉ phù hợp nếu khoảng [r, l] rất nhỏ.

Cách Inclusion-Exclusion Principle (Nguyên lý Bù trừ)

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

long long countDiv(long long l, long long r, long long k) {
   return r / k - (l - 1) / k;
}

int main() {
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   freopen("countdiv.inp", "r", stdin);
   freopen("countdiv.out", "w", stdout);
   int t; cin >> t;
   long long l, r, a, b;
   while (t--) {
      cin >> l >> r >> a >> b;
      long long lcm_ab = lcm(a, b);
      long long ans = countDiv(l, r, a)
                    + countDiv(l, r, b)
                    - countDiv(l, r, lcm_ab);
      cout << ans << endl;
   }
   return 0;
}

• Time Complexity: O(Q * log(min(a, b)))
• Space Complexity: O(1)

Solution thứ 3 sử dụng kỹ thuật Bù trừ. Số lượng số chia hết cho a trong đoạn [l, r] là: floor(r/a) - floor((l-1)/a). Tương tự cho b. Tuy nhiên, các số chia hết cho cả a và b (bội chung của a và b) bị đếm 2 lần. Ta phải trừ đi số lượng số chia hết cho Bội chung nhỏ nhất (LCM) của a và b. Công thức: Ans = SL(a) + SL(b) - SL(lcm(a, b)). Độ phức tạp phụ thuộc vào hàm tính LCM, thường là O(log(min(a, b))) do sử dụng GCD.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán đếm số lượng số chia hết cho k trong đoạn [l, r] có công thức trực tiếp: r/k - (l-1)/k.
• Khi đếm số lượng số chia hết cho A hoặc B, ta phải trừ đi các số chia hết cho cả A và B (trùng lặp) bằng cách dùng Bội chung nhỏ nhất (LCM).

Lỗi thường gặp

• Brute Force sẽ gây ra Time Limit Exceeded (TLE) nếu khoảng [l, r] lớn (ví dụ 10^12).
• Lỗi tràn số (overflow) khi tính bội chung nhỏ nhất nếu không dùng kiểu dữ liệu lớn (long long). Công thức lcm(a, b) = (a * b) / gcd(a, b).