acwing873. 欧拉函数874. 筛法求欧拉函数

本文主要是介绍acwing873. 欧拉函数874. 筛法求欧拉函数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

873. 欧拉函数

欧拉函数定义：

代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>using namespace std;typedef long long LL;int main ()
{// vector<int> prime;int n;cin >> n;while (n--){unordered_map<int, int> prime;int a;cin >> a;LL res = a;// cout << res << endl;for (int i = 2; i <= a/i; ++i){while (a%i == 0){a /= i;prime[i] ++;}}if (a > 1) prime[a] ++;for (auto p : prime){int t = p.first;res = res/t*(t-1);// cout << res << endl;}cout << res << endl;}
}

874. 筛法求欧拉函数

当i是质数的时候，i的倍数的质数就是i的倍数乘（i-1）/ i。其实就是我们上面提到的公式。所以代码如下：

    for (int i = 2; i <= MAXN; ++i){if (phi[i] == i) // i is prime{for (int j = i; j <= MAXN; j += i){phi[j] = phi[j] / i * (i - 1);}}}

全部代码如下：

#include <iostream>
#include <vector>using namespace std;typedef long long LL;const int MAXN = 1000000;
int phi[MAXN + 1];void initPhi()
{for (int i = 1; i <= MAXN; ++i)phi[i] = i;for (int i = 2; i <= MAXN; ++i){if (phi[i] == i) // i is prime{for (int j = i; j <= MAXN; j += i){phi[j] = phi[j] / i * (i - 1);}}}
}int main()
{int n;cin >> n;initPhi();LL sum = 0;for (int i = 1; i <= n; ++i){sum += phi[i];}cout << sum << endl;return 0;
}

这篇关于acwing873. 欧拉函数874. 筛法求欧拉函数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---