[传送门: BZOJ3994]
简要题意:
给出 n,m, 设 d(x) 为 x 的约数个数, 求 $\sum_{i=1}^{n}\sum_{j=1}^{m}d(i*j)$
题解:
莫比乌斯反演, 设 n<m
yy 一下可以发现 $d(i*j)=\sum_{x|i}\sum_{y|j}1[gcd(x,y)==1]$
然后原式就等于 $$\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x|i}\sum_{y|j}1[gcd(x,y)==1]$$
先枚举 x,y, 得到 $$\sum_{x=1}^{n}\sum_{y=1}^{m}\frac{n}{i}*\frac{m}{j}[gcd(x,y)==1]$$
因为 $\sum_{d|x}\mu(d)=[x==1]$
所以得到 $$\sum_{x=1}^{n}\sum_{y=1}^{m}\frac{n}{i}*\frac{m}{j}\sum_{d|gcd(i,j)}\mu(d)$$
先枚举 d, 得到 $$\sum_{d=1}^{n}\mu(d)\sum_{x=1}^{n}[d|x]\sum_{y=1}^{m}[d|y]\frac{n}{x}*\frac{m}{y}$$
$$\sum_{d=1}^{n}\mu(d)\sum_{x=1}^{\frac{n}{d}}\frac{n}{d*x}*\sum_{y=1}^{\frac{m}{d}}\frac{m}{d*y}$$
显然最前面一项可以预处理, 设 $S(x)=\sum_{i=1}^{x}\frac{x}{i}$, 得到 $$\sum_{d=1}^{n}\mu(d)*S(\frac{n}{d})*S(\frac{m}{d})$$
S(x) 可以 $O(n*\sqrt{n})$ 预处理, 但是实际上可以在线性筛的时候顺便处理
因为我们发现 $S(x)=\sum_{i=1}^{x}d(i)$, 只要求出 d(i) 就可以了
参考代码:
- #include<cstdio>
- #include<cstring>
- #include<cstdlib>
- #include<cmath>
- #include<algorithm>
- using namespace std;
- typedef long long LL;
- int miu[51000],prime[51000],v[51000];
- LL d[51000];int c[51000];
- void pre(int n)
- {
- int m=0;miu[1]=d[1]=c[1]=1;
- for(int i=2;i<=n;i++)
- {
- if(v[i]==0)
- {
- v[i]=i;c[i]=1;d[i]=2;
- prime[++m]=i;
- miu[i]=-1;
- }
- for(int j=1;j<=m;j++)
- {
- if(prime[j]>v[i]||prime[j]>n/i) continue;
- v[i*prime[j]]=prime[j];
- if(i%prime[j]==0) miu[i*prime[j]]=0,d[i*prime[j]]=d[i]/(c[i]+1)*(c[i]+2),c[i*prime[j]]=c[i]+1;
- else miu[i*prime[j]]=-miu[i],d[i*prime[j]]=d[i]*d[prime[j]],c[i*prime[j]]=1;
- }
- }
- for(int i=1;i<=n;i++) miu[i]+=miu[i-1],d[i]+=d[i-1];
- }
- int main()
- {
- pre(50000);
- int T;
- scanf("%d",&T);
- while(T--)
- {
- int n,m;
- scanf("%d%d",&n,&m);if(n>m) swap(n,m);
- LL ans=0;
- for(int i=1,j;i<=n;i=j+1)
- {
- j=min(n/(n/i),m/(m/i));
- ans+=(LL)(miu[j]-miu[i-1])*d[n/i]*d[m/i];
- }
- printf("%lld\n",ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2820892.html