P2158 [SDOI2008]仪仗队

P2158 [SDOI2008]仪仗队
图是关于y=x对称的,横纵坐标一定是互质的否则在之前就被扫过了,所以就可以用欧拉函数再*2就完了。

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<set>
#include<map>
#include<stack>
#include<cstring>
#define inf 2147483647
#define For(i,a,b) for(register int i=a;i<=b;i++)
#define p(a) putchar(a)
#define g() getchar()
//by war
//2017.11.3
using namespace std;
int n;
int ans;
int prime[];
bool vis[];
int cnt,tot;
int pr[];
void in(int &x)
{
int y=;
char c=g();x=;
while(c<''||c>'')
{
if(c=='-')
y=-;
c=g();
}
while(c<=''&&c>='')x=(x<<)+(x<<)+c-'',c=g();
x*=y;
}
void o(int x)
{
if(x<)
{
p('-');
x=-x;
}
if(x>)o(x/);
p(x%+'');
} void Euler()
{
For(i,,n)
{
if(!vis[i])prime[++cnt]=i;
for(register int j=;j<=cnt&&i*prime[j]<=n;j++)
{
vis[i*prime[j]]=true;
if(i%prime[j]==)
break;
}
}
} int Eulerfunction(int x)
{
tot=;
int c=x;
For(i,,cnt)
{
if(prime[i]>x)
break;
if(x%prime[i]==)
pr[++tot]=prime[i];
}
For(i,,tot)
c=c-c/pr[i];
return c;
} int main()
{
in(n);
n--;
Euler();
For(i,,n)
ans+=Eulerfunction(i);
o(ans*+);
return ;
}
上一篇:Java序列化小结


下一篇:使用JQuery 合并两个 json 对象