2190: [SDOI2008]仪仗队

Time Limit: 10 Sec  Memory Limit: 259 MB
[Submit][Status][Discuss]

Description

  作为体育委员,C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图)。    bzoj 2190: [SDOI2008]仪仗队 线性欧拉函数-LMLPHP   现在,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 ;
}
05-11 13:42