题目描述
作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 
现在，C君希望你告诉他队伍整齐时能看到的学生人数。
分析就不写了都写得很《《《《全》》》》了
就当看模板叭
#include<iostream> #include<cstdio> using namespace std; typedef long long ll; int rd(){ ll x=0,fl=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')fl=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*fl; } int n,ans,cnt,pri[40100],ex[40100],phi[40100]; /*ola打表*/ void ola(){ ex[0]=ex[1]=1;cnt=0; for(int i=2;i<=n;i++){ if(!ex[i]){ pri[++cnt]=i;//如果是素数的话，它的欧拉函数就等于他自己-1 phi[i]=i-1; } for(int j=1;j<=cnt&&pri[j]*i<=n;j++){ ex[pri[j]*i]=1; if(i%pri[j])phi[i*pri[j]]=phi[i]*(pri[j]-1);//下面是不是素数的情况下分两种情况讨论的递推公式 else{ phi[i*pri[j]]=phi[i]*pri[j]; break; } } } } int ola2(int n){ if(n==1)return 1; int ans=n,k=1; for(int i=2;n!=1;i+=k) if(!(n%i)){ ans/=i;ans*=(i-1); while(!(n%i)) n/=i; i=k; } return ans; } int main(){ n=rd(); ola(); for(int i=2;i<n;i++) ans+=phi[i]; // for(int i=2;i<n;i++) // ans+=ola2(i); // 另一种做法（好慢。。 printf("%d",ans*2+3); return 0; }