POJ3090 巧用欧拉函数 phi(x)

POJ3090 给定一个坐标系范围 求不同的整数方向个数

分析： 除了三个特殊方向（y轴方向 x轴方向 （1，1）方向）其他方向的最小向量表示（x,y）必然互质

所以对欧拉函数前N项求和 乘2（关于（1，1）对称）再+3就是答案

给出代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long int LL;

LL getPrime(bool notprime[],LL prime[],LL N)

{

 LL tot=0;

 for(LL i=2;i<=N;i++)

   {

    if(!notprime[i]) prime[tot++]=i;

    for(LL j=0;j<tot;j++)

       {

        if(prime[j]*i>N)break;

        notprime[prime[j]*i]=true;

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

	   }

   }

 return tot;

}

LL pow_mod(LL n,LL k,LL p)

{

 if(k==0)return 1;

 LL w=1;

 if(k&1)w=n%p;

 LL ans=pow_mod(n*n%p,k>>1,p);

 return ans*w%p;

}

bool Miller_Rabin(LL n,LL a,LL d)

{

 if(n==2)return true;

 if(n==a)return true;

 if(n%a==0)return false;

 if((n&1)==0)return false;

 while(!(d&1))d=d>>1;

 LL t=pow_mod(a,d,n);

 if(t==1)return true;//特别注意！！

 while((d!=n-1)&&(t!=1)&&(t!=n-1))

 		{

 		 t=(LL)t*t%n;

		 d=d<<1;

		}

 return (t==n-1||(d&1)==1);

}

bool isPrime(LL n,LL times)

{

 if(n<2)return false;

 LL a[4]={2,3,5,7};

 for(LL i=0;i<4;i++){if(!Miller_Rabin(n,a[i],n-1))return false;}

 return true;

}

void Factor(LL n,LL a[],LL b[],LL &tot)

{

 LL temp,i,now;

 temp=(LL)((double)sqrt(n)+1);

 tot=0;

 now=n;

 for(i=2;i<=temp;i++)

 	if(now%i==0)

	 	{

	 	 a[tot]=i;

	 	 b[tot]=0;

	 	 while(now%i==0)

	 	 	{

	 	 	 b[tot]++;

	 	 	 now/=i;

			}

		 tot++;

		}

	if(now!=1)

		{

		 a[tot]=now;

		 b[tot++]=1;

		}

}

LL digitsum(LL n)

{

 LL ans=0;

 for(LL i=0;;i++)

 	{

 	 LL div=pow(10,i);

 	 if((n/div)==0)return ans;

 	 ans+=(n%(div*10))/div;

	}

}

void getPhi(LL mindiv[],LL phi[],LL max)

{

 max=max+1;

 for(LL i=1;i<max;i++)

    mindiv[i]=i;

 for(LL i=2;i<(LL)(sqrt(max)+1);i++)

 	{

 	 if(mindiv[i]==i)

 	 	{

 	 	 for(LL j=i*i;j<max;j+=i)

 	 	    mindiv[j]=i;

		}

	}

 memset(phi,0,sizeof(phi));

 phi[1]=1;

 for(LL i=2;i<max;++i)

 	{

 	 phi[i]=phi[i/mindiv[i]];

 	 if(((i/mindiv[i])%mindiv[i])==0)phi[i]*=mindiv[i];

 	 	else phi[i]*=mindiv[i]-1;

	}

}

void getMobius(LL mu[],LL max)

{

 for(LL i=1;i<=max;i++)

 	{

 	 LL target=i==1?1:0;

 	 LL delta=target-mu[i];

 	 mu[i]=delta;

 	 for(LL j=i+i;j<=max;j+=i)

 	    mu[j]+=delta;

	}

}

LL mindiv[1001],phi[1001];

int main()

{

 //freopen("t.txt","r",stdin);

 //freopen("1.txt","w",stdout);

 getPhi(mindiv,phi,1000);

 LL sum[1001];

 sum[1]=0;

 sum[2]=1;

 for(int i=3;i<=1000;i++)

    sum[i]=sum[i-1]+phi[i];

 int np;

 scanf("%d",&np);

 for(int i=1;i<=np;i++)

 	{

 	 int now;

 	 scanf("%d",&now);

 	 LL ans=sum[now]*2+3;

 	 printf("%d %d %lld\n",i,now,ans);

	}

 return 0;

}