Cerința

Vi se dau n perechi de numere naturale (i, j), cu i ≤ j. Pentru fiecare pereche trebuie să aflați suma divizorilor tuturor numerelor din șirul i, i + 1, ..., j.

Date de intrare

Fișierul de intrare eratostene0.in conține pe prima linie numărul n, iar pe următoarele n linii câte două numere naturale i1 j1, i2 j2, …, in jn.

Date de ieșire

Fișierul de ieșire eratostene0.out va conține n linii, pe fiecare linie L, L = 1..n, aflându-se un singur număr natural reprezentând suma divizorilor tuturor numerelor corespunzătoare perechii iL jL.

Restricții și precizări

• 1 ≤ n ≤ 200.000
• 1 ≤ i ≤ j ≤ 1.000.000

Exemplu

eratostene0.in

4
1 6
3 7
2 5
8 8

eratostene0.out

33
37
20
15

Explicație

1 are suma divizorilor 1.
2 are suma divizorilor 3.
3 are suma divizorilor 4.
4 are suma divizorilor 7.
5 are suma divizorilor 6.
6 are suma divizorilor 12.
7 are suma divizorilor 8.
8 are suma divizorilor 15.

Pentru perechea 1 6 trebuie să aflăm suma divizorilor tuturor numerelor din șirul 1,2,3,4,5,6. Această sumă este 33.
Pentru perechea 3 7 trebuie să aflăm suma divizorilor tuturor numerelor din șirul 3,4,5,6,7. Această sumă este 37.
Pentru perechea 2 5 trebuie să aflăm suma divizorilor tuturor numerelor din șirul 2,3,4,5. Această sumă este 20.
Pentru perechea 8 8 trebuie să aflăm suma divizorilor tuturor numerelor din șirul format doar din 8. Această sumă este 15.

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

ifstream cin("eratostene0.in");
ofstream cout("eratostene0.out");

long long  S[1000001];

int main(){
    int n;
    cin >> n;
    S[1] = 1;
    for(int i = 2; i <= 1000000; ++i)
        S[i] = i + 1;
    for(int i = 2; i * i <= 1000000; ++i){
        S[i * i] = S[i * i] + i;
        for(int j = i + 1; j * i <= 1000000; j++)
            S[i * j] = S[i * j] + i + j;
    }
    for(int i = 1; i <= 1000000; ++i)
        S[i] += S[i-1];
    int x, y;
    for(int i = 1; i <= n; ++i){
        cin >> x >> y;
        cout << S[y] - S[x-1] << '\n';
    }
    return 0;
}