Subtask ~3~:

• Với ~l, r, t \le 10^6~, ta cần tính tổng các ~G_i~ trong ~O(1)~.
• Sử dụng tư tưởng sàng Eratosthenes, với mỗi ~i~ là số nguyên tố, ta cộng ~i~ vào tổng ước của các bội của ~i~.
• Kết hợp sàng với kỹ thuật tổng tiền tố, ta có thể vượt qua với độ phức tạp ~O(t \times \log r)~.

Code tham khảo

#include <bits/stdc++.h> 
using namespace std;
typedef int64_t ll;
const int mod = 1e9 + 7;

ll sum[1000005];

void prepare() {
    for (int i = 2; i <= 1000000; i++) {
        if (sum[i] == 0) {
            for (int j = i; j <= 1000000; j += i) {
                sum[j] = (sum[j] + i) % mod;
            }
        }
    }
    for (int i = 2; i <= 1000000; i++) sum[i] += sum[i - 1];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("sumdiv.inp", "r", stdin);
    freopen("sum.out", "w", stdout);
    prepare();
    int t; cin >> t;
    while (t--) {
        int l, r;
        cin >> l >> r;
        cout << (sum[r] - sum[l - 1] + mod) % mod << '\n';
    }
    return 0;
}