BZOJ 4804: 欧拉心算 欧拉函数

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10000001;
int phi[N+10], pr[N+10], tot;
bool np[N+10];
long long s[N+10];
void getphi() {
    int i, j;
    phi[1] = 1;
    for(i=2;i<=N;i++) {
        if(!np[i]) {
            pr[++tot] = i;
            phi[i] = i-1;
        }
        for(j=1;j<=tot&&i*pr[j]<=N;j++) {
            np[i*pr[j]]=1;
            if(i%pr[j] == 0) {
                phi[i*pr[j]]=phi[i]*pr[j];
                break;
            }
            else
                phi[i*pr[j]]=phi[i]*(pr[j] - 1);
        }
    }
    for(i=1;i<=N;i++) {
        s[i]=s[i-1]+phi[i];
    }
}
int main() {
    int t;
    scanf("%d",&t);
    getphi();
    while(t--) {
        int n;
        long long ans=0;
        scanf("%d",&n);
        int lst =0;
        for(int p=1;p<=n;p=lst+1) {
            lst = n/(n/p);
            ans+=(s[lst]-s[p-1])*(s[n/p]*2-1);
        }
        printf("%lld\n",ans);
    }
    
}