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 ;

}