Hướng dẫn giải

Cho đoạn $[L, R]$ với $R \le 10^9$, cần tính tổng các số trong đoạn không chia hết cho $13$. Cách nghĩ tự nhiên là tổng mọi số trừ tổng các bội của $13$.

Sub 1: Vét cạn — ~O(R - L)~, dùng khi ~R \le 10^7~

Duyệt từng số $x$ trong $[L, R]$, nếu $x$ không chia hết cho $13$ thì cộng vào tổng. Đúng với mọi đoạn, nhưng với $R$ lớn thì chậm.

Nếu chỉ nộp sub này: đúng 21/22 test (test lớn bị quá giờ, các test còn lại đúng).

Sub 2: Công thức — ~O(1)~

• Tổng mọi số trong $[L, R]$: $\dfrac{(L+R)(R-L+1)}{2}$.
• Các bội của $13$ trong $[L, R]$ là $13k$ với $k$ từ $k1 = \lceil L/13 \rceil$ đến $k2 = \lfloor R/13 \rfloor$. Tổng các $k$ là một dãy số liên tiếp, bằng $\dfrac{(k1+k2)(k2-k1+1)}{2}$ (tích luôn chẵn nên chia $2$ được), và tổng các bội là $13$ lần tổng đó.
• Đáp án = tổng mọi số $-$ tổng các bội của $13$.

Bẫy cần chú ý: tổng có thể lên tới khoảng $10^{18}$ nên dùng long long. Khi $L = 0$ thì $0$ là bội của $13$, công thức vẫn đúng. Nếu không có bội nào trong đoạn ($k1 > k2$) thì tổng các bội bằng $0$.

Chương trình hoàn chỉnh

Chương trình đọc $L, R$. Nếu $R \le 10^7$ thì gọi sub1, ngược lại gọi sub2. Khi đi thi, sub1 vẫn ăn điểm các test nhỏ nếu chưa làm được công thức.

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

long long L, R;

// Sub 1: vét cạn — duyệt từng số trong [L, R], cộng các số không chia hết cho 13
// Dùng khi R <= 10^7
void sub1() {
    long long sum = 0;
    for (long long x = L; x <= R; x++)
        if (x % 13 != 0) sum += x;
    cout << sum << "\n";
}

// Sub 2: công thức — tổng tất cả các số trong [L, R] trừ tổng các bội của 13
// Tổng dãy số liên tiếp từ p đến q: (p + q) * cnt / 2 (tích luôn chẵn nên chia 2 được)
void sub2() {
    long long total = (L + R) * (R - L + 1) / 2;

    // các bội của 13 trong [L, R] là 13*k với k từ k1 đến k2
    long long k1 = (L + 12) / 13;   // k nhỏ nhất với 13k >= L
    long long k2 = R / 13;          // k lớn nhất với 13k <= R
    long long sumK = 0;
    if (k1 <= k2) {
        long long cnt = k2 - k1 + 1;
        sumK = (k1 + k2) * cnt / 2;   // tổng các k
    }
    long long multSum = 13 * sumK;    // tổng các bội của 13
    cout << total - multSum << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> L >> R;
    if (R <= 10000000) sub1();   // đoạn nhỏ: vét cạn
    else sub2();                 // đoạn lớn: công thức O(1)
    return 0;
}