AcWing 201. 可见的点
原题链接
简单
作者:
geats兔
,
2024-04-10 11:41:57
,
所有人可见
,
阅读 1
C++ 代码
#include <iostream>
#include <cstring>
const int N = 1010;
int primes[N],st[N],cnt;
int Eluer[N];
void init(int n)
{
Eluer[1]=1;
for (int i = 2; i <= n; i ++ )
{
if(!st[i])
{
primes[cnt++]=i;
Eluer[i]=i-1;
}
for (int j = 0; primes[j] <= n/i; j ++ )
{
st[i*primes[j]]=true;
if(i%primes[j]==0)
{
Eluer[i*primes[j]]=Eluer[i]*primes[j];
break;
}
Eluer[i*primes[j]]=Eluer[i]*(primes[j]-1);
}
}
}
int main()
{
init(N-1);
int c;scanf("%d",&c);
for(int i=1;i<=c;i++)
{
int n;scanf("%d",&n);
int res=0;
for (int i = 1; i <= n; i ++ )
{
res+=Eluer[i];
}
printf("%d %d %d\n",i,n,2*res+1);
}
return 0;
}