BZOJ2190: [SDOI2008]仪仗队

Portal

仔细观察一下图发现，若某个点可取，那么它的横纵坐标的最大公约数为1. 可以想到欧拉函数。

【代码】

#include <iostream> #include <cstdio> #include <algorithm> #define N 40005 #define mod 1000000007 #define INF 0x7fffffff using namespace std; typedef long long ll; typedef pair<int,int> pa; int read() { int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } int n,ans; int p[N],not_Prime[N]={1,1},phi[N]; void getphi() { phi[1]=1; for(int i=2;i<=n;i++) { if(!not_Prime[i]) p[++p[0]]=i,phi[i]=i-1; for(int j=1;i*p[j]<=n&&j<=p[0];j++) { not_Prime[i*p[j]]=1; if(!(i%p[j])) { phi[i*p[j]]=phi[i]*p[j]; break; } phi[i*p[j]]=phi[i]*phi[p[j]]; } } } int main() { n=read(); getphi(); for(int i=1;i<n;i++) ans+=phi[i]<<1; printf("%d\n",ans+1); return 0; }