【模板】杜教筛(Sum)
2022/3/9 23:19:23
本文主要是介绍【模板】杜教筛(Sum),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
\(\text{Code}\)
#include<cstdio> #include<tr1/unordered_map> #define LL long long using namespace std; const int M = 5e6; int vis[M + 5],p[M + 5],tot,T,n; LL phi[M + 1],mu[M + 1]; tr1::unordered_map<int,LL> fm,fp; void init() { mu[1] = phi[1] = 1LL; for (int i = 2; i <= M; i++) { if (!vis[i]) p[++tot] = i,mu[i] = -1,phi[i] = i - 1; for (int j = 1; j <= tot && p[j] * i <= M; j++) { vis[p[j] * i] = 1; if (i % p[j] == 0) {phi[i * p[j]] = phi[i] * p[j]; break;} mu[p[j] * i] = -mu[i],phi[i * p[j]] = phi[i] * phi[p[j]]; } } for (int i = 1; i <= M; i++) mu[i] += mu[i - 1],phi[i] += phi[i - 1]; } LL getmu(int x) { if (x <= M) return mu[x]; if (fm[x]) return fm[x]; LL res = 1LL; for (LL l = 2,r; l <= x; l = r + 1) r = x / (x / l),res -= (LL)(r - l + 1) * getmu(x / l); return fm[x] = res; } LL getp(int x) { if (x <= M) return phi[x]; if (fp[x]) return fp[x]; LL res = (LL)x * (x + 1LL) / 2; for (LL l = 2,r; l <= x; l = r + 1) r = x / (x / l),res -= (LL)(r - l + 1) * getp(x / l); return fp[x] = res; } int main() { init(),scanf("%d",&T); for (; T; T--) scanf("%d",&n),printf("%lld %lld\n",getp(n),getmu(n)); }
这篇关于【模板】杜教筛(Sum)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行