题目链接 https://lydsy.com/JudgeOnline/problem.php?id=3944
problem
给出一个 \(n,n <2^{31}\). 分别求
- \[\sum\limits_{
- i=1
- }^n\varphi(i),\sum\limits_{
- i=1
- }^n\mu(i)\]
- solution
\(\varphi(i)\) 和 \(\mu(i)\) 都是积性函数.
且 \(\varphi(p^k)=(p-1)p^{k-1}\), 所以可以直接 \(Min\_25\) 筛了.
因为 \(\varphi(p)=p-1,p 是质数 \),g 函数不好处理
所以将 \(\varphi(p)\) 分为两个函数 \(f_1(p)=p,f_2(p)=1\). 然后分别求 \(g\) 和 \(h\).
\(\mu\) 预处理就直接是 \(-h\) 了.
然后 \(Min\_25\) 筛模板就行了.
RP--
- code
- /*
- * @Author: wxyww
- * @Date: 2019-12-25 20:16:31
- * @Last Modified time: 2019-12-25 21:38:39
- */
- #include<cstdio>
- #include<iostream>
- #include<cstdlib>
- #include<cstring>
- #include<algorithm>
- #include<queue>
- #include<vector>
- #include<ctime>
- #include<cmath>
- using namespace std;
- typedef long long ll;
- const int N = 500010;
- ll read() {
- ll x = 0,f = 1;char c = getchar();
- while(c <'0' || c> '9') {
- if(c == '-') f = -1; c = getchar();
- }
- while(c>= '0' && c <= '9') {
- x = x * 10 + c - '0'; c = getchar();
- }
- return x * f;
- }
- ll m,n,pri[N],vis[N],JS,tot,g[N],h[N],sum[N];
- void pre() {
- for(int i = 2;i <= 500000;++i) {
- if(!vis[i]) pri[++JS] = i,sum[JS] = sum[JS - 1] + i;
- for(int j = 1;j <= JS && 1ll * pri[j] * i <= 500000;++j) {
- vis[pri[j] * i] = 1;
- if(i % pri[j] == 0) break;
- }
- }
- }
- ll w[N],id1[N],id2[N];
- ll Sphi(ll now,ll x) {
- if(now <= 1 || pri[x]> now) return 0;
- ll k;
- if(now <= m) k = id1[now];
- else k = id2[n / now];
- ll ret = g[k] - h[k] - sum[x - 1] + x - 1;
- for(int k = x;k <= tot && pri[k] * pri[k] <= now;++k) {
- ll p = pri[k];
- for(int e = 1;p * pri[k] <= now;++e,p *= pri[k]) {
- ret += (pri[k] - 1) * (p / pri[k]) * Sphi(now / p,k + 1) + p * (pri[k] - 1);
- }
- }
- return ret;
- }
- ll Smu(ll now,ll x) {
- if(now <= 1 || pri[x]> now) return 0;
- ll k;
- if(now <= m) k = id1[now];
- else k = id2[n / now];
- ll ret = -h[k] + x - 1;
- for(int k = x;k <= tot && pri[k] * pri[k] <= now;++k) {
- ret -= Smu(now / pri[k],k + 1);
- }
- return ret;
- }
- void solve() {
- m = sqrt(n);
- if(!n) return (void)puts("0 0");
- tot = 0;
- // memset(g,0,sizeof(g));memset(h,0,sizeof(h));
- for(ll l = 1,r;l <= n;l = r + 1) {
- r = n / (n / l);
- w[++tot] = n / l;
- if(n / l <= m) id1[n / l] = tot;
- else id2[r] = tot;
- g[tot] = ((w[tot] + 2) * (w[tot] - 1)) / 2;
- h[tot] = w[tot] - 1;
- }
- // puts("!!");
- for(int j = 1;j <= JS && pri[j] <= m;++j) {
- for(int i = 1;i <= tot && 1ll * pri[j] * pri[j] <= w[i];++i) {
- ll tmp = w[i] / pri[j];
- int k;
- if(tmp <= m) k = id1[tmp];
- else k = id2[n / tmp];
- g[i] -= pri[j] * (g[k] - sum[j - 1]);
- h[i] -= h[k] - j + 1;
- }
- }
- // for(int i = 1;i <= tot;++i) printf("%lld",h[i]);
- // puts("");
- // puts("!");
- cout<<Sphi(n,1) + 1 <<" "<<Smu(n,1) + 1<<endl;
- // puts("!!!");
- }
- int main() {
- int T = read();
- pre();
- while(T--) {
- n = read();solve();
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3350252.html