2190: [SDOI2008]仪仗队
Time Limit: 10 Sec Memory Limit: 259 MB
[Submit][Status][Discuss]
Description
作为体育委员,C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 现在,C君希望你告诉他队伍整齐时能看到的学生人数。
Input
共一个数N。
Output
共一个数,即C君应看到的学生人数。
Sample Input
4
Sample Output
9
HINT
【数据规模和约定】 对于 100% 的数据,1 ≤ N ≤ 40000
思路:求gcd(x,y)==1 1<=x,y<=N;
ans=2*sigma(phi[i])+2-1;
ps:我以为N==1的时候为0;然而并没有1这样的数据;
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define esp 1e-10
const int N=1e5+,M=1e6+,mod=1e9+,inf=1e9+;
ll p[M],ji;
bool vis[M];
ll phi[M];
void get_eular(int n)
{
ji = ;
memset(vis, true, sizeof(vis));
for(int i = ; i <= n; i++)
{
if(vis[i])
{
p[ji ++] = i;
phi[i] = i - ;
}
for(int j = ; j < ji && i * p[j] <= n; j++)
{
vis[i * p[j]] = false;
if(i % p[j] == )
{
phi[i * p[j]] = phi[i] * p[j];
break;
}
else
phi[i * p[j]] = phi[i] * phi[p[j]];
}
}
}
ll sumphi[M];
int main()
{ ll x,y,z,i,t;
get_eular();
phi[]=;
sumphi[]=;
for(i=;i<=;i++)
sumphi[i]=sumphi[i-]+phi[i];
while(~scanf("%lld",&x))
{
if(x==)
printf("0\n");
else
printf("%lld\n",*sumphi[x-]+);
}
return ;
}