NATDIV (Segment Tree)

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

const int N = 1e6 + 1;

long long a[N], b[N];

int main()
{
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL); cout.tie(NULL);
    //freopen("NATDIV.inp", "r", stdin);
    //freopen("NATDIV.inp", "w", stdout);

    for (int i = 1; i*i <= N; ++i){
        a[i*i] += i;
        b[i*i] += 1;
        for (int j = i + 1; i*j <= N; ++j){
            a[i*j] += i + j;
            b[i*j] += 2;
        }
    }

    for (int i = 2; i <= N; ++i){
        a[i] += a[i - 1];
        b[i] += b[i - 1];
    }

    long long t; cin >> t;
    while (t--)
    {
        int l, r; cin >> l >> r;
        cout << b[r] - b[l - 1] << ' ' << a[r] - a[l - 1] << '\n';
    }

    return 0;
}