首页 > 其他 > 详细

BZOJ-2190 [SDOI2008]仪仗队

时间:2015-05-05 21:18:22      阅读:200      评论:0      收藏:0      [点我收藏+]

数论。。。

答案就是前n-1个欧拉函数的总和再*2+1

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <iostream>
#define rep(i, l, r) for(int i=l; i<=r; i++)
#define clr(x, c) memset(x, c, sizeof(x))
#define maxn 45678
using namespace std;
inline int read()
{
	int x=0, f=1; char ch=getchar();
	while (!isdigit(ch)) {if (ch==‘-‘) f=-1; ch=getchar();}
	while (isdigit(ch)) x=x*10+ch-‘0‘, ch=getchar();
	return x*f;
}
int f[maxn];
int main()
{
	int n=read()-1, ans=0; 
	rep(i, 1, n) f[i]=i;
	rep(o, 2, n) if (f[o]==o) for(int i=o; i<=n; i+=o) f[i]=f[i]/o*(o-1);
	rep(i, 1, n) ans+=f[i]; 
	if (!n) printf("0\n"); else printf("%d\n", ans*2+1);
	return 0;
}

BZOJ-2190 [SDOI2008]仪仗队

原文:http://www.cnblogs.com/NanoApe/p/4479902.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!