HDU 1286 找新朋友

Sol：歐拉函數的應用。。。。

#include   
#include   
  
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;i1)  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;
}