hdu1286 找新朋友 （欧拉函数法）

本文主要是介绍hdu1286 找新朋友 （欧拉函数法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题：点击打开链接

关于欧拉函数的算法详细讲解：点击打开链接

欧拉函数

1.欧拉函数是不完全积性函数。

2.欧拉函数p(x) = x * (p1 - 1) / p1 * (p2 - 1)/p2 * .....(pn - 1)/ pn;

#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;int euler(int x)//Euler 模板
{int i, res = x;for(i = 2; i < (int) sqrt(x * 1.0)+1; i++)if(x % i == 0){res = res / i * (i - 1);while(x % i == 0) x /= i; // 保证i一定是素数}if(x > 1)res = res / x * (x - 1);return res;
}
int main()
{int x;int Case;cin >> Case;while(Case--){while(cin >> x){cout <<euler(x) << endl;}}return 0;
}

这篇关于hdu1286 找新朋友 （欧拉函数法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---