题目描述:
设\(d(x)\)为\(x\)的约数个数,给定\(n,m\),求\(\sum_{i=1}^n\sum_{j=1}^md(ij)\)
首先有一个前置知识:
\(d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]\)
所以原式等于:
\(\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]\)
反演以下:
\(\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}\sum_{d|gcd(x,y)}\mu(d)\)
交换求和顺序:
\(\sum_{d=1}^n\mu(d)\sum_{x=1}^n\sum_{y=1}^m[d|gcd(x,y)][n/x][m/y]\)
然后可以把枚举\(x,y\)改为枚举\(d\)的倍数,把\([d|gcd(x,y)]\)这个玩意去掉:
\(\sum_{d=1}^n\mu(d)\sum_{x=1}^{n/d}\sum_{y=1}^{m/d}[n/dx][m/dy]\)
把与x有关的项,与y有关的项合并,有
\(\sum_{d=1}^n\mu(d)\sum_{x=1}^{n/d}[n/dx]\sum_{y=1}^{m/d}[m/dy]\)
然后套莫反笔记的引理1:
\(\sum_{d=1}^n\mu(d)\sum_{x=1}^{n/d}[[n/d]/x]\sum_{y=1}^{m/d}[[m/d]/y]\)
这里我们设\(p=n/d,q=m/d\):
\(\sum_{d=1}^n\mu(d)\sum_{x=1}^p[p/x]\sum_{y=1}^q[q/y]\)
设\(f(x)=\sum_{i=1}^x[x/i]\)
\(\sum_{d=1}^n\mu(d)f(p)f(q)\)
这里\(p=[n/d]\),\(q=[m/d]\),所以可以对\(d\)进行数论分块,同一个块内的\(p\)和\(q\)可以快速计算。
现在预处理求\(f(x)\)。暴力时间复杂度是\(O(n^2)\)的。
观察\(f(x)=\sum_{i=1}^x[x/i]\),同一块内\(x/i\)的值不变,所以对每个\(x\)可以数论分块求。
时间复杂度\(O(n\sqrt{n}+T\sqrt{n})\)。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
typedef long long ll;
int vis[maxn],pri[maxn],mu[maxn],sum[maxn],cnt;
ll f[maxn];
void getMu (int n) {
mu[1]=1;
for (int i=2;i<=n;i++) {
if (!vis[i]) {
mu[i]=-1;
pri[++cnt]=i;
}
for (int j=1;j<=cnt&&i*pri[j]<=n;j++) {
vis[i*pri[j]]=1;
if (i%pri[j]==0) break;
else mu[i*pri[j]]=-mu[i];
}
}
for (int i=1;i<=n;i++) sum[i]=sum[i-1]+mu[i];
for (int i=1;i<=n;i++) {
for (int l=1,r;l<=i;l=r+1) {
r=i/(i/l);
f[i]+=1ll*(r-l+1)*(i/l);
}
}
}
int main () {
int _;
getMu(5e4);
scanf("%d",&_);
while (_--) {
int n,m;
scanf("%d%d",&n,&m);
if (n>m) swap(n,m);
ll ans=0;
for (int l=1,r;l<=n;l=r+1) {
r=min(n/(n/l),m/(m/l));
ans+=1ll*f[n/l]*f[m/l]*(sum[r]-sum[l-1]);
}
printf("%lld\n",ans);
}
}