BZOJ 2190: [SDOI2008]仪仗队

starli posted @ 2016年2月04日 22:02 in 数学 , 185 阅读

有一个结论 一个点(x,y)到原点 经过gcd(x,y)个点 自己试一下就知道了 

于是这题只要求一下$(\sum_{i=1}^{n-1}phi(i)*2)+1$就好了 n的范围很小没必要用线性筛

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=40010;
int p[N],phi[N],n,vis[N],ans;
int main(){
	scanf("%d",&n);
	phi[1]=p[1]=1;
	for(int i=2;i<=n;i++) if(!vis[i]){
			p[i]=1;
			phi[i]=i-1;
			for(int j=2;j*i<=n;j++){
				if(!phi[i*j]) phi[i*j]=i*j;
				vis[i*j]=1;
				phi[i*j]=phi[i*j]*(i-1)/i;
			}
		}
	for(int i=1;i<n;i++) ans+=phi[i]*2;
	printf("%d",ans+1);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter