#include<iostream> #include<algorithm> using namespace std; const int M=1e6; int vis[M+4],P[M+4],cnt; int fi[M+4]; void shai(int top){ cnt=0; fi[1]=1; for(int i=2;i<=top;i++){ if(vis[i]==0){ P[++cnt]=i; fi[i]=i-1; } for(int j=1;j<=cnt&&i*P[j]<=top;j++){ vis[i*P[j]]=1; if(i%P[j]==0){ fi[i*P[j]]=fi[i]*P[j]; break; } else fi[i*P[j]]=fi[i]*(P[j]-1); } } } int sum[M+4]; int main(){ shai(1e6); for(int i=1;i<=1e6;i++) sum[i]=sum[i-1]+fi[i]; int tes,cas=0;cin>>tes; while(tes--){ int x; cin>>x; cout<<++cas<<' '<<x<<' '<<2*sum[x]+1<<endl; } }
标签:cnt,int,Visible,3090,Points,poj,fi,tes From: https://www.cnblogs.com/towboa/p/17303216.html