BZOJ 2190([SDOI2008]仪仗队-O(n)线性筛欧拉函数)

2190: [SDOI2008]仪仗队

Time Limit: 10 Sec   Memory Limit: 259 MB

Submit: 521  

Solved: 331

[​​Submit​​][​​Status​​][​​Discuss​​]

Description

　　作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 　　 

 　　现在，C君希望你告诉他队伍整齐时能看到的学生人数。

Input

　　共一个数N。

Output

　　共一个数，即C君应看到的学生人数。

Sample Input

　　4

Sample Output

　　9

HINT

【数据规模和约定】 
　　对于 100% 的数据，1 ≤ N ≤ 40000 

线性筛欧拉函数的方法相信大家都懂

这里不赘述

总而言之，这题就是求有多少(i,j)满足gcd(i,j)=1,i<n,j<n,正宗欧拉函数。。。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<functional>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXN (40000+10)
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
int n,a[MAXN],size=0,phi[MAXN]={0};
bool b[MAXN]={0};
int get_phi()
{
  phi[1]=1;
  Fork(i,2,n)
  {
    if (!b[i])
    {
      a[++size]=i;phi[i]=i-1;
    }
    For(j,size)
    {
      if (i*a[j]>MAXN) break;
      b[i*a[j]]=1;
      if (i%a[j]==0) 
      {
        phi[i*a[j]]=phi[i]*a[j];break;
      }
      else phi[i*a[j]]=phi[i]*(a[j]-1);
    }
  }
}
int main()
{
  cin>>n;
  get_phi();
  long long sum=0;
  For(i,n-1) sum+=phi[i];
  sum=sum*2+(n>=2);
//  For(i,n) cout<<phi[i]<<' ';
  cout<<max(sum,(long long)0)<<endl;
  
  return 0;
}