[BZOJ 2190]仪仗队
转载请注明出处：http://danihao123.is-programmer.com/
这个题啊……有规律可循。
我们可以发现，关于答案[tex]a[/tex]有如下规律：
[tex]a+1=2\mul (\Sigma_{i=2}^{n-1}\varphi(i)+2)[/tex]
然后筛法求欧拉函数即可（我听说神犇们都用了杜教筛哎）
代码：
/**************************************************************
Problem: 2190
User: danihao123
Language: C++
Result: Accepted
Time:28 ms
Memory:976 kb
****************************************************************/
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=40005;
#define CUS_REP(i,a,b) for(i=(a);i<=(b);i++)
int phi[maxn];
int n;
void sieve(){
register int i,j;
phi[1]=1;
CUS_REP(i,2,n)
if(!phi[i])
for(j=i;j<=n;j+=i){
if(!phi[j])
phi[j]=j;
phi[j]=phi[j]/i*(i-1);
}
}
int main(){
register int i,ans=2;
scanf("%d",&n);
sieve();
/*
#ifdef DEBUG
CUS_REP(i,1,n)
printf("%d\n",phi[i]);
#endif
*/
CUS_REP(i,2,n-1)
ans+=phi[i];
printf("%d\n",ans*2-1);
return 0;
}
评论 (0)
