Tóm tắt đề bài

Cho bốn số nguyên dương \(a, b, x, y\). Yêu cầu đếm số lượng các số nguyên \(k\) trong đoạn \([a, b]\) sao cho \(k\) chia hết cho \(x\) hoặc \(k\) chia hết cho \(y\) (hoặc cả hai).

Phân tích

• Giới hạn: \(a, b, x, y \le 10^9\). Với giới hạn này, việc duyệt qua từng số trong đoạn \([a, b]\) để kiểm tra điều kiện chia hết là không khả thi vì độ phức tạp sẽ là \(O(b-a)\), có thể lên tới \(10^9\) phép tính.
• Nguyên lý bù trừ (Inclusion-Exclusion Principle): Để đếm số lượng phần tử chia hết cho \(x\) hoặc \(y\), ta sử dụng công thức:
  • Gọi \(S_x\) là tập các số chia hết cho \(x\) trong đoạn \([a, b]\).
  • Gọi \(S_y\) là tập các số chia hết cho \(y\) trong đoạn \([a, b]\).
  • Số lượng cần tìm là \(|S_x \cup S_y| = |S_x| + |S_y| - |S_x \cap S_y|\).
• Giao của hai tập hợp: Một số chia hết cho cả \(x\) và \(y\) khi và chỉ khi nó chia hết cho bội chung nhỏ nhất của \(x\) và \(y\), ký hiệu là \(BCNN(x, y)\) (hay \(LCM(x, y)\)).

Hướng giải quyết

1. Đếm số lượng số chia hết cho \(k\) trong đoạn \([1, N]\)

Số lượng các số nguyên dương không vượt quá \(N\) và chia hết cho \(k\) được tính bằng công thức:

2. Đếm số lượng số chia hết cho \(k\) trong đoạn \([a, b]\)

Dựa vào tính chất của đoạn, ta có:

3. Áp dụng nguyên lý bù trừ

• Số lượng số chia hết cho \(x\): \(N_x = \lfloor \frac{b}{x} \rfloor - \lfloor \frac{a-1}{x} \rfloor\)
• Số lượng số chia hết cho \(y\): \(N_y = \lfloor \frac{b}{y} \rfloor - \lfloor \frac{a-1}{y} \rfloor\)
• Số lượng số chia hết cho cả \(x\) và \(y\): \(N_{xy} = \lfloor \frac{b}{L} \rfloor - \lfloor \frac{a-1}{L} \rfloor\), với \(L = BCNN(x, y)\).
• Công thức tính \(BCNN(x, y)\):
  
  \[ BCNN(x, y) = \frac{x \times y}{UCLN(x, y)} \]
• Kết quả cuối cùng: \(N_x + N_y - N_{xy}\).

Độ phức tạp

• Thời gian: \(O(\log(\min(x, y)))\) do sử dụng thuật toán Euclid để tìm \(UCLN\). Với các số đến \(10^9\), phép tính này cực kỳ nhanh.
• Bộ nhớ: \(O(1)\).