HDU 1286 找新朋友

Sol：欧拉函数的应用。。。。

#include <cstdio>  
#include <cstring>  
  
using namespace std;  
  
const int maxisp = 1000 + 10;  
const int maxp = 500 + 10;  
  
int num,n;  
int prime[maxp];  
int isprime[maxisp];  
  
inline void get_prime()  
{  
    num=0;  
    for(int i=2;i<=maxisp;i++)  
        if(!isprime[i])  
        {  
            prime[num++]=i;  
            for(int j=1;j*i<=maxisp;j++)  
                isprime[i*j]=1;  
        }  
}  
  
inline int euler(int x)  
{  
    int res=x;  
    for(int i=0;i<num&&prime[i]*prime[i]<=x;i++)  
    {  
        if(x%prime[i]==0)  
        {  
            res=res/prime[i]*(prime[i]-1);  
            while(x%prime[i]==0)  
                x/=prime[i];  
        }  
    }  
    if(x>1)  res=res/x*(x-1);  
    return res;  
}

int main()
{
	get_prime();
	int T,ans;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&ans);
		printf("%d\n",euler(ans));
	}
	return 0;
}

HDU 1286 找新朋友

原文：http://blog.csdn.net/imutzcy/article/details/18951333