Tóm tắt đề bài

Cho dãy số có quy luật: \(3, 4, 6, 7, 9, 10, 12, 13, \dots\). Yêu cầu tính tổng các số trong dãy này có giá trị nằm trong khoảng \((A, B)\), tức là các số \(x\) thuộc dãy sao cho \(A < x < B\).

Phân tích

• Quy luật dãy số:
  • Dãy số bắt đầu từ 3.
  • Khoảng cách giữa các số hạng liên tiếp luân phiên là \(+1\) rồi \(+2\).
  • Cụ thể: \(3 \xrightarrow{+1} 4 \xrightarrow{+2} 6 \xrightarrow{+1} 7 \xrightarrow{+2} 9 \xrightarrow{+1} 10 \dots\)
• Nhận xét quan trọng:
  • Các số trong dãy là các số nguyên dương không chia hết cho 3, bắt đầu từ 3. Tuy nhiên, nếu nhìn kỹ hơn: \(3, 4, 6, 7, 9, 10, \dots\) thực chất là tập hợp các số nguyên dương \(n \ge 3\) mà \(n\) không chia hết cho 3 dư 2 (như \(5, 8, 11, \dots\) không xuất hiện) là sai.
  • Hãy xem lại:
    • Các số chia hết cho 3: \(3, 6, 9, 12, \dots\) (Dạng \(3k\))
    • Các số chia 3 dư 1: \(4, 7, 10, 13, \dots\) (Dạng \(3k+1\))
    • Các số chia 3 dư 2: \(5, 8, 11, 14, \dots\) (Dạng \(3k+2\)) - Không có trong dãy.
  • Vậy dãy số bao gồm tất cả các số nguyên \(x \ge 3\) sao cho \(x \pmod 3 \neq 2\).
• Giới hạn: \(A, B \le 2 \times 10^8\). Với giới hạn này, ta không thể duyệt từng số từ \(A\) đến \(B\) vì sẽ bị quá thời gian (TLE). Cần một công thức toán học tính nhanh.

Hướng giải quyết

1. Công thức tính tổng

Gọi \(S(N)\) là tổng các số thuộc dãy quy luật trên mà \(\le N\).
Tổng các số trong khoảng \((A, B)\) sẽ là:

2. Cách tính \(S(N)\)

Dãy các số \(\le N\) bao gồm hai nhóm:

• Nhóm 1: Các số chia hết cho 3: \(3, 6, 9, \dots, 3k \le N\).
• Nhóm 2: Các số chia 3 dư 1: \(4, 7, 10, \dots, 3m+1 \le N\).

Nhóm 1 (Cấp số cộng): \(3, 6, 9, \dots, 3 \cdot \lfloor \frac{N}{3} \rfloor\).

• Số hạng đầu \(u_1 = 3\), số hạng cuối \(u_k = 3 \cdot \lfloor \frac{N}{3} \rfloor\).
• Số lượng số hạng: \(k = \lfloor \frac{N}{3} \rfloor\).
• Tổng \(T_1 = \frac{(u_1 + u_k) \cdot k}{2}\).

Nhóm 2 (Cấp số cộng): \(4, 7, 10, \dots, u_m \le N\).

• Số hạng đầu \(v_1 = 4\).
• Nếu \(N < 4\), tổng \(T_2 = 0\).
• Nếu \(N \ge 4\), số hạng cuối \(v_m\) là số lớn nhất \(\le N\) có dạng \(3m+1\). Công thức: \(v_m = \lfloor \frac{N-1}{3} \rfloor \cdot 3 + 1\).
• Số lượng số hạng: \(m = \lfloor \frac{N-1}{3} \rfloor\).
• Tổng \(T_2 = \frac{(v_1 + v_m) \cdot m}{2}\).

Kết quả: \(S(N) = T_1 + T_2\).

Độ phức tạp

• Thời gian: \(O(1)\) do chỉ sử dụng công thức toán học.
• Bộ nhớ: \(O(1)\).

Code tham khảo

#include <iostream>

using namespace std;

/**

 * Hàm tính tổng các số trong dãy (3, 4, 6, 7, 9, 10...) mà <= N
 * Dãy gồm các số chia hết cho 3 (3, 6, 9...) và các số chia 3 dư 1 (4, 7, 10...)
 */
long long calculate_S(long long N) {
    if (N < 3) return 0;

    // Tổng nhóm chia hết cho 3: 3, 6, 9, ..., 3*k <= N
    long long k = N / 3;
    long long last1 = k * 3;
    long long T1 = (3 + last1) * k / 2;

    // Tổng nhóm chia 3 dư 1: 4, 7, 10, ..., 3*m + 1 <= N
    long long T2 = 0;
    if (N >= 4) {
        long long m = (N - 1) / 3;
        long long last2 = m * 3 + 1;
        // m là số lượng số hạng: (4, 7, ..., last2)
        // Số lượng thực tế là m, nhưng m tính từ (N-1)/3 sẽ bắt đầu từ 1 (số 4)
        T2 = (4 + last2) * (m - 1 + 1) / 2; 
    }

    return T1 + T2;
}

int main() {
    long long A, B;
    if (!(cin >> A >> B)) return 0;

    // Đề bài yêu cầu: A < x < B
    // Kết quả = S(B-1) - S(A)
    if (A >= B - 1) {
        cout << 0 << endl;
    } else {
        cout << calculate_S(B - 1) - calculate_S(A) << endl;
    }

    return 0;
}

Giải thích thêm về công thức Nhóm 2:

Với \(N=8\):

• Nhóm 1: \(3, 6\) (\(k=2\)). \(T_1 = (3+6) \cdot 2 / 2 = 9\).
• Nhóm 2: \(4, 7\) (\(m = \lfloor (8-1)/3 \rfloor = 2\)). \(v_m = 2 \cdot 3 + 1 = 7\). \(T_2 = (4+7) \cdot 2 / 2 = 11\).
• \(S(8) = 9 + 11 = 20\).
• Ví dụ \(A=2, B=8 \Rightarrow\) Tính \(S(7) - S(2)\).
  • \(S(7): T_1 (3, 6) = 9, T_2 (4, 7) = 11 \Rightarrow S(7) = 20\).
  • \(S(2): 0\).
  • Kết quả: \(20 - 0 = 20\) (Khớp với ví dụ).