Contest1331/D.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;
    }
}