题解 P2158 【[SDOI2008]仪仗队】

intruder · 2016-07-04 07:48:19 · 题解

首先 你可以先画个图 然后就会发现 所有能够看到的点都满足 他的横坐标和纵坐标互素（把第一排定为下标0） 然后就是关键求出 1<=x<=n中 比x小且与x互素的个数了 然后加起来乘二加一（自己想）

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n;
int phi[40005];
void work(){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!phi[i])
        for(int j=i;j<=n;j+=i){
            if(!phi[j])phi[j]=j;
            phi[j]=phi[j]/i*(i-1);
        }
    }
}
int main(){
    scanf("%d",&n);
    work();
    long long ans=0;
    for(int i=1;i<=n-1;i++)ans+=(long long)phi[i];
    printf("%lld",2*ans+1);
    return 0;
}