HDU 1286 找新朋友（欧拉函数模板）

HDU 1286 找新朋友（欧拉函数模板）2015-02-17HDU 1286 找新朋友：http://acm.hdu.edu.cn/showproblem.php？pid=1286

题意：中文题。

思路：欧拉函数的纯模板题，没什么好说的，主要是理解欧拉函数的意义。

在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler"s totient function、φ函数、欧拉商数等。例如φ（8）=4，因为1,3,5,7均和8互质。 ----by度娘。

#include <stdio.h> int eular（int n）{int ret = 1;for（int 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 T, n; int main（）{scanf（"%d", &T）;while（T--）{scanf（"%d", &n）;printf（"%d
", eular（n））;} return 0;} ///HDU 1286

From：cnblogs GLSilence