Contest1343/E.cpp

#include <bits/stdc++.h>
 
using namespace std;
vector<int> phi;
 
void genPhi(int max) {
    int minDiv[max];
    for (int i = 1; i < max; i++) {
        minDiv[i] = i;
    }
    for (int i = 2; i * i < max; i++) {
        if (minDiv[i] == i) {
            for (int j = i * i; j < max; j += i) {
                minDiv[j] = i;
            }
        }
    }
    phi[1] = 1;
    for (int i = 2; i < max; i++) {
        phi[i] = phi[i / minDiv[i]];
        if ((i / minDiv[i]) % minDiv[i] == 0) {
            phi[i] *= minDiv[i];
        } else {
            phi[i] *= minDiv[i] - 1;
        }
    }
}
 
const int MAXN = 1000001;
long long g[MAXN];
int f[MAXN];
 
int main() {
//    ofstream cout("output.txt");
    phi.resize(MAXN);
    genPhi(MAXN);
    for (int i = 1; i <= MAXN; i += 2) {
        f[i] = phi[i] % (i + 1);
    }
    g[0] = 0;
    for (int i = 1; i <= MAXN; i++) {
        g[i] = g[i - 1] + f[i];
    }
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        int n;
        cin >> n;
        cout << "Case " << t << ": " << g[n] << endl;
    }
}