LightOJ - Mathematically Hard

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

const int maxN = 5 * 1e6 + 1;
unsigned long long phi[maxN];

void preComputePhi () {
    for (unsigned long long i = 1; i < maxN; ++i) phi[i] = i;
    for (unsigned long long i = 2; i < maxN; ++i) {
        if (phi[i] == i) {
            for (unsigned long long j = i; j < maxN; j += i) {
                phi[j] -= phi[j] / i;
            }
        }
    }
    for (int i = 1; i < maxN; ++i) phi[i] = phi[i] * phi[i];
    for (int i = 1; i < maxN; ++i) phi[i] += phi[i - 1];
}

int main () {
     ios::sync_with_stdio(false);
     cin.tie(nullptr) ;
     cout.tie(nullptr);
     int T;
     cin >> T;
     preComputePhi();
     for (int test_case = 1; test_case <= T; ++test_case) {
         int a,b;
         cin >> a >> b;
         cout << "Case " << test_case << ": " << (phi[b] - phi[a - 1]) << '\n';
     }
     //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}