bzoj3944 Sum
程序员文章站
2022-03-30 23:02:45
"题目链接" problem 给出一个$n,n include include include include include include include include using namespace std; typedef long long ll; const int N = 50001 ......
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; }
推荐阅读
-
sum(case when then)(判断男女生的个数)
-
sql中count或sum为条件的查询示例(sql查询count)
-
linux比较两个文件是否一样(linux命令md5sum使用方法)
-
mysql踩坑之limit与sum函数混合使用问题详解
-
Python中使用md5sum检查目录中相同文件代码分享
-
[codewars_python]Sum of Digits / Digital Root
-
基于Python中求和函数sum的用法详解
-
对python中array.sum(axis=?)的用法介绍
-
python 列表,数组和矩阵sum的用法及区别介绍
-
sum(case when then)(判断男女生的个数)