Tóm tắt đề bài

Cho hai số tự nhiên \(a\) và \(b\) (\(1 \leq a \leq b \leq 10^6\)). Hãy đếm xem trong đoạn từ \(a\) đến \(b\) có bao nhiêu số chia hết cho 3.

Phân tích

• Giới hạn: \(a, b \leq 10^6\). Với giới hạn này, ta có thể sử dụng vòng lặp chạy từ \(a\) đến \(b\) để kiểm tra từng số. Tuy nhiên, cách tối ưu hơn là sử dụng công thức toán học để giải quyết bài toán trong thời gian hằng số.
• Tính chất: Số lượng các số chia hết cho \(k\) trong đoạn \([1, n]\) được tính bằng công thức:
  
  \[ f(n) = \lfloor \frac{n}{k} \rfloor \]
  
  Trong đó \(\lfloor x \rfloor\) là phần nguyên của \(x\).

Hướng giải quyết

Cách 1: Sử dụng công thức toán học (Tối ưu)

Để tìm số lượng số chia hết cho 3 trong đoạn \([a, b]\), ta có thể tính:

1. Số lượng số chia hết cho 3 trong đoạn \([1, b]\) là: \(count_b = \lfloor \frac{b}{3} \rfloor\).
2. Số lượng số chia hết cho 3 trong đoạn \([1, a-1]\) là: \(count_{a-1} = \lfloor \frac{a-1}{3} \rfloor\).
3. Kết quả cần tìm là hiệu của hai giá trị trên:
   
   \[ Ans = \lfloor \frac{b}{3} \rfloor - \lfloor \frac{a-1}{3} \rfloor \]

Cách 2: Sử dụng vòng lặp (Duyệt)

Vì \(b \leq 10^6\), ta có thể duyệt từ \(a\) đến \(b\), nếu số nào chia hết cho 3 thì tăng biến đếm. Cách này vẫn đảm bảo thời gian chạy trong giới hạn cho phép (thường là 1 giây cho \(10^8\) phép tính).

Độ phức tạp

• Thời gian: \(O(1)\) nếu dùng công thức toán học, hoặc \(O(b-a)\) nếu dùng vòng lặp. Cả hai đều thỏa mãn yêu cầu.
• Bộ nhớ: \(O(1)\).

Code tham khảo

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

int main() {
    // Tối ưu tốc độ nhập xuất
    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0);

    long long a, b;
    if (!(cin >> a >> b)) return 0;

    // Sử dụng công thức: f(b) - f(a-1)
    // f(n) là số lượng số chia hết cho 3 trong khoảng [1, n]
    long long result = (b / 3) - ((a - 1) / 3);

    cout << result << endl;

    return 0;
}