hdu 1286

 

欧拉函数：找出小于或等于n与n互质的数的个数， 例如φ(8)=4，因为1,3,5,7均和8互质

code:

#include <iostream>
#include "math.h"
using namespace std;
typedef long long LL;
LL euler(LL n )
{ 
	LL i,m = (int)sqrt( n + 0.5 ),ans = n;
	for( i = 2; i <= m; i++ ) 
		if( n%i == 0 )
		{ 
			ans = ans/i*(i-1); while( n%i == 0 ) n /= i;
		} 
	if( n > 1 ) ans = ans/n*(n-1); return ans;
}
    
int main(int argc, char *argv[])
{
	int t;
	scanf("%d\n",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		cout<<euler(n)<<endl;
	}
	return 0;
}