筛法求欧拉函数之和
2022/7/24 6:24:07
本文主要是介绍筛法求欧拉函数之和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
求\(1\sim n\)每个数欧拉函数之和
想法
- 如果\(i\)是质数
\(\varphi (i) = i - 1\)
质数\(i\)只有\(1\)和\(i\)两个因数,\(i\)不和\(i\)本身互质,因数只有一个\(1\),所以互质的数就有\(i-1\)个
- 如果\(i\)不是质数
- \(i \% j = 0\)
\(j\)是质数
则\(j\)即\(i\)的一个质因子,所以\(\varphi (i)\)中已经包含了\(j\)\(\varphi (j \times i) = j\times i\times (1-\frac{1}{p_1})\times(1-\frac{1}{p_2})\times…\times(1-\frac{1}{p_k}))\)①
因为$\varphi (i) =i\times (1-\frac{1}{p_1})\times(1-\frac{1}{p_2})\times…\times(1-\frac{1}{p_k}) \(② 将②代入①中得: \)\varphi (j \times i) = j \times \varphi (i)$
- \(i \% j \neq 0\)
则\(j\)不是\(i\)的质因子,根据线性筛
中的推导,\(j\)是\(j \times i\)的最小质因子所以\(\varphi(j\times i)=\varphi (i) \times \varphi (j)\)
由1可得,如果\(j\)是质数:\(\varphi (j) = j - 1\)
\(\varphi(j\times i)= \varphi (i) \times (j - 1)\)
发现过程中有关质因数,想到线性筛
所以我们可以套用线性筛的板子
码来!
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1e6+10; typedef long long LL; int primes[N], idx; // 记录质数,idx是下标 int phi[N]; // 存储每个欧拉函数的值 bool st[N]; // 是否是质数 LL get_phi(int n) { phi[1] = 1; for (int i = 2; i <= n; i ++ ) { if(!st[i]) // 如果i是质数 { primes[idx++] = i; phi[i] = i - 1; } for (int j = 0; primes[j] <= n / i; j ++ ) { int t = primes[j] * i; st[t] = true; if(i % primes[j] == 0) // j是i的质因数的情况 { phi[t] = phi[i] * primes[j]; break; } // j不是i的质因数的情况 phi[t] = phi[i] * (primes[j] - 1); } } LL res = 0; // 用longlong类型存储 —— 怕爆int for(int i = 1; i <= n; i++) { res += phi[i]; // 计算从1到n的欧拉函数之和 } return res; } int main() { int n; cin >> n; LL ans = get_phi(n); printf("%lld\n", ans); return 0; }
欢迎大佬指出本蒟蒻的错误!
这篇关于筛法求欧拉函数之和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?