AcWing201. 可见的点【欧拉筛模板】

传送门
存个板子

int n,prime[1010],cntprime,vis[1010],phi[1010];
LL sum[1010];

void solve(int Case){
    n=read();
    printf("%d %d %lld
",Case,n,sum[n]*2+1);
}

int main(){
    phi[1]=1;
    for(int i=2;i<=1e3;i++){
        if(!vis[i]) vis[i]=1,prime[++cntprime]=i,phi[i]=i-1;
        for(int j=1;prime[j]*i<=1e3;j++){
            vis[prime[j]*i]=1;
            if(i%prime[j]==0) {phi[i*prime[j]]=phi[i]*prime[j];break;}
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    for(int i=1;i<=1010;i++) sum[i]=sum[i-1]+phi[i];
    int T=read();
    for(int i=1;i<=T;i++) solve(i);
    return 0;
}