BZOJ 2190儀仗隊【歐拉函數】

問題的唯一難點就是如何表示隊長能看到的人數？如果建系，隊長所在的點為（0,0）分析幾組數據就一目了然了，如果隊長能看到的點為(m,n),那么gcd（m，n）=1即m n 互質或者是（0,1），（1,0）兩點。證明很簡單，如果gcd（m，n）=d 那么(m/d,n/d)必然會擋住點（m，n），所以gcd（m，n）=1是必然的。這樣問題就劃歸到2到n-1有多少數互質。由于歐拉函數的意義是小于n的與n互質的數的個數，所以知道歐拉函數意義的人都能第一時間想到答案就是t=φ（2）+φ（3）+…+φ（n-1） ，如果點（m，n）可以被看到，根據對稱性（n，m）也可以被看到，再加上(1,1)(由于(1,1)是唯一不具有對稱性的點所以分開來考慮)（0,1），（1,0）三點，所以答案 ans=t*2+3 ，如果定義φ（1）=1 那么答案就是φ（1）+φ（2）+φ（3）+…+φ（n-1）+1了

?

?

#include<iostream>

#include<cstdio>

#include <math.h>

using namespace std;

int prime[20000]={0},t;

bool isprime(int k)

{

????for (int i=1;i<=t-1;i++)

???? {

????????if (k % prime[i]==0)return false;

???? }

????return true;

}

int euler(int k)

{

???????? intnow=1,e=1,i;

???????? while(k!=1)

???????? {

?????????????????? for(i=now;i<=t-1;i++)

?????????????????? {

??????????????????????????? now++;

??????????????????????????? if(k % prime[i]==0)break;

?????????????????? }

???????e=e*(prime[i]-1);k=k/prime[i];

???????while (k % prime[i]==0)

?????????????????? {

??????????????????????????? e=e*prime[i];

??????????????????????????? k=k/prime[i];

?????????????????? }

???????? }

???????? returne;

}

int main()

{

???????? t=2;

???int m,n,i,ans=0;

???scanf("%d",&n);

???prime[1]=2;

???

???for (i=2;i<=40000;i++)

??? {

???????m=i*2-1;

?? ?????if (isprime(m))

???????{

???????????prime[t]=m;

???????????t++;

???????}

??? }

???????? for(i=1;i<=n-1;i++)

???????? {

?????????????????? ans+=euler(i);

???????? }

???????? ans=ans*2+1;

???printf("%d",ans);

???return 0;

}

?