什么是欧拉函数? 见 百度百科
就是这样的一个函数, 在ACM里面算是一个常见内容了(虽然目前我只见过一次).
那么我们定义Φ(n)为n的欧拉函数
那么显然的, 如果n是质数, Φ(n) = n - 1, 如果n不是质数, 那么我们只要求出n的所有因数, 即可求出Φ(n).
这么看来求欧拉函数就是分解质因数 + 计算了.
有没有更方便, 更快速的方法呢?
有的! 我们可以把求欧拉函数和素数筛法结合起来. 这就是所谓欧拉筛法.
for (long long i = 1; i <= n; ++i) {Euler[i] = i;}for (long long i = 2; i <= n; ++i) { // 普通筛法i * i <= n没错的, 但是这是欧拉筛,所有约数都要出现 if (prim[i] == 0) {for (long long j = i + i; j <= n; j += i) {prim[j] = 1;Euler[j] = Euler[j] * (i - 1) / i;}}}for (int i = 2; i <= n; ++i) {if (prim[i] == 0) Euler[i]--;}
一道欧拉筛法的模板题 仪仗队
#include <algorithm>#include <iostream>#include <vector>using namespace std;const int maxn = 40000 + 5;bool prim[maxn] = {};long long n, Euler[maxn], ans = 0;int main(){cin >> n;if (n == 1) {cout << 0;return 0;}for (long long i = 1; i <= n; ++i) {Euler[i] = i;}for (long long i = 2; i <= n; ++i) { // 普通筛法i * i <= n没错的, 但是这是欧拉筛,所有约数都要出现 if (prim[i] == 0) {for (long long j = i + i; j <= n; j += i) {prim[j] = 1;Euler[j] = Euler[j] * (i - 1) / i;}}}for (int i = 2; i <= n; ++i) {if (prim[i] == 0) Euler[i]--;}for (int i = 2; i < n; ++i) {ans += Euler[i];}cout << 2 * ans + 3;}
如果觉得《欧拉函数_互质数》对你有帮助，请点赞、收藏，并留下你的观点哦！
