hdu1286 找新朋友 欧拉函数的应用

点击打开hdu1286找新朋友

思路：欧拉函数裸题，可以知道欧拉函数是用来求1~n中与n互质的数的个数。

#include<stdio.h>
#include<stdlib.h>
int eular(int n)
{int ret=1,i;for(i=2;i*i<=n;i++){if(n%i==0){n/=i,ret*=i-1;while(n%i==0) n/=i,ret*=i;}}if(n>1) ret*=n-1;return ret;
}
int main ()
{int n,s;int t;scanf("%d",&t);while(t--){scanf("%d",&n);s=eular(n);printf("%d\n",s);}return 0;
}