AcWing 874 筛法求欧拉函数
发布日期:2021-05-28 16:27:02 浏览次数:9 分类:技术文章

本文共 1452 字,大约阅读时间需要 4 分钟。

题目描述:

给定一个正整数n,求1~n中每个数的欧拉函数之和。

输入格式

共一行,包含一个整数n。

输出格式

共一行,包含一个整数,表示1~n中每个数的欧拉函数之和。

数据范围

1≤n≤10^6

输入样例:

6

输出样例:

12

分析:

求1到n中每个数的欧拉函数之和,显然一个个调用计算欧拉函数的公式时间复杂度是极高的。可以通过修改素数的线性筛法的代码来实现欧拉函数的求和功能,线性筛法将每个数都筛了一遍,所以可以在筛的过程中计算出欧拉函数。欧拉函数phi(n) = n(1 - 1/p1 +... + 1/pk),对于素数而言,小于它的数都与之互质,所以i为质数时,phi(i) = i - 1.当i去筛掉t = i*primes[j]时,分为i能被primes[j]整除和不能被其整除两种情况。primes[j] | i时,primes[j]为i的因子,所以t中出现的质数在i中都出现了,即phi(i) = i(1 - 1 / p1 + ... + 1 / pk),phi(t) = t(1 - 1 / p1 + ... + 1 / pk) = phi(i) * t / i = phi(i)*primes[j]。i不能被primes[j]整除时,i必然与primes[j]互质(因为primes存储的都是质数),则t中恰好比i多一个primes[j]的质因子,即phi(i) = i(1 - 1 / p1 + ... + 1 / pk),phi(t) = t(1 - 1 / p1 + ... + 1 / pk) (1 - 1 / primes[j])= phi(i) * (1 - 1 / primes[j]) * t / i = phi(i)*(primes[j] - 1)。

#include 
using namespace std;typedef long long ll;const int maxn = 1000005;int primes[maxn],euler[maxn],cnt;bool st[maxn];void get_eulers(int n){ euler[1] = 1; for(int i = 2;i <= n;i++){ if(!st[i]){ primes[cnt++] = i; euler[i] = i - 1; } for(int j = 0;primes[j] <= n / i;j++){ int t = i * primes[j]; st[t] = true; if(i % primes[j] == 0){ euler[t] = euler[i] * primes[j]; break; } euler[t] = euler[i] * (primes[j] - 1); } }}int main(){ int n; cin>>n; get_eulers(n); ll res = 0; for(int i = 1;i <= n;i++) res += euler[i]; cout<
<

 

转载地址:https://blog.csdn.net/qq_30277239/article/details/103696711 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:AcWing 875 快速幂
下一篇:AcWing 873 欧拉函数

发表评论

最新留言

逛到本站,mark一下
[***.202.152.39]2024年02月09日 12时22分49秒