解题报告（Codeforces Round #146 (Div. 1) E. Number Challenge 莫比乌斯反演）数论

题目链接

题意：
给定n,m,l，求
文章图片

d(x)：x的约数个数

思路：
加强版的约数个数和（解题报告：BZOJ_3994 约数个数和莫比乌斯反演学习题）？

代入公式
文章图片

得到
文章图片

得到
文章图片

代入常用的公式：
文章图片

得到：
文章图片

这个式子的复杂度为
文章图片

但是可以发现对于一个数k，只需要用到和它互质的部分
那么可以在
文章图片
的时间内预处理出每个数的互质的所有的数

那么就能在
文章图片
的时间内得出结果
总复杂度
文章图片

代码：

#includeconst long long mod = (1LL<<30)-1; const int N = 2005; using namespace std; vectorpr,coprime[N]; bool Np[N]; int mu[N]; void init(){ mu[1] = 1; for(int i=1; im)swap(n,m); long long ans = 0; for(int d=1,lastd; d<=n; d=lastd+1){ lastd = d; long long sum = 0; for(int idk=0,k=coprime[d][0]; k<=l; k=coprime[d][++idk]){ int edn = n/d , edm = m/d ; int ed = max(edn,edm) ; long long tmpn = 0 , tmpm = 0; for(int idi=0,i=coprime[k][0]; i<=ed; i=coprime[k][++idi]){ if(i<=edn)tmpn = (tmpn+(edn/i))&mod; if(i<=edm)tmpm = (tmpm+(edm/i))&mod; }sum += ( ( 1LL * (l/k) * tmpn & mod )* tmpm ) & mod; }sum *=mu[d]; sum&=mod; ans += sum; }printf("%I64d\n",ans&mod); }

【解题报告（Codeforces Round #146 (Div. 1) E. Number Challenge 莫比乌斯反演）】