AcWing 201. 可见的点
原题链接
简单
作者:
吴鑫
,
2021-02-11 09:53:49
,
所有人可见
,
阅读 354
#include<iostream>
#include<cstring>
using namespace std;
const int N=1010;
int prime[N],cut;
int phi[N];
bool st[N];
int c,n;
int phi_prime(){
memset(st,0,sizeof st);cut=0;
phi[1]=1;
for(int i=2;i<=n;i++){
if(!st[i]){
prime[cut++]=i;
phi[i]=i-1;
}
for(int j=0;prime[j]<=n/i;j++){
st[prime[j]*i]=true;
if(i%prime[j]==0){
phi[prime[j]*i]=phi[i]*prime[j];
break;
}
phi[prime[j]*i]=phi[i]*(prime[j]-1);
}
}
int res=0;
for(int i=1;i<=n;i++) res+=phi[i];
return 2*res+1;
}
int main(){
cin>>c;
for(int i=1;i<=c;i++){
cin>>n;
printf("%d %d %d\n",i,n,phi_prime());
}
return 0;
}