BZOJ 2190 欧拉函数

思路：

递推出来欧拉函数

搞个前缀和

sum[n-1]*2+3就是答案

假设仪仗队是从零开始的

视线能看见的地方就是gcd(x,y)=1的地方

倒过来一样 刨掉(1,1) 就是ans*2+1 再加一下第零行第零列的两个

就是结果了

//By SiriusRen

#include <cstdio>

using namespace std;

#define N 40005

int n,prime[N],vis[N],phi[N],tot;

long long ans;

int main(){

    scanf("%d",&n);

    for(int i=2;i<n;i++){

        if(!vis[i])phi[i]=i-1,prime[++tot]=i;

        for(int j=1;j<=tot&&i*prime[j]<n;j++){

            vis[i*prime[j]]=1,phi[i*prime[j]]=phi[i]*(prime[j]-1);

            if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}

        }

        ans+=(long long)phi[i];

    }

    ans=ans*2+3;

    printf("%lld\n",ans);

}