【题解】[SDOI2015] 约数个数和 莫比乌斯反演 luogu3327 –Qiuly

又是一道神奇的题目。

一句话题意：给定 $n,m$ 求 $\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij)$

于是开始推式子：

有这么一条公式：

$$d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$$

这个非常重要，至于证明的话，本人太弱，留个坑，到时候再填，请大家谅解 $QwQ$ 。

然后呢？发现题目求的式子后面正好是 $d(ij)$ ，于是美滋滋的套进去。

$$\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x|i}\sum_{y|j}[gcd(i,j)=1]$$

$x$ 和 $y$ 我们扔到前面去枚举，后面来计算它们对它们的倍数做出的贡献。

可以知道前面的 $x$ 在 $n$ 以内的倍数有 $\lfloor\frac{n}{x}\rfloor$ 个，$y$ 在 $m$ 以内的倍数有 $\lfloor\frac{m}{y}\rfloor$，于是：

$$\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x|i}\sum_{y|j}[gcd(i,j)=1]$$

$$=\sum_{x=1}^{n}\sum_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\cdot[gcd(i,j)=1]$$

按照套路，我们设：

$$f(x)=\sum_{x=1}^{n}\sum_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\cdot[gcd(i,j)=k]$$

$$g(k)=\sum_{x=1}^{n}\sum_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\cdot[k|gcd(i,j)]$$

那么显然有：

$$g(k)=\sum_{k|d} f(d)$$

这个式子很有熟悉的味道，显然是反演常见的第二种形式。

所以就有：

$$f(k)=\sum_{k|d}\mu(\frac{d}{k})g(d)$$

我们的答案是 $f(1)$，那么就是：

$$f(1)=\sum_{d=1}^{n}\mu(d)g(d)$$

现在来考虑怎么计算 $g$ 。

$$g(k)=\sum_{x=1}^{n}\sum_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\cdot[k|gcd(i,j)]$$

后面的 $k$ 很碍眼，消掉他。

$$g(k)=\sum_{x=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{k}\rfloor}\lfloor\frac{n}{xk}\rfloor\lfloor\frac{m}{yk}\rfloor$$

于是我们预处理一个函数 $s$ ：

$$s(k)=\sum_{i=1}^{k}\lfloor\frac{k}{i}\rfloor$$

那么 $g(k)$ 就很好算了：

$$g(k)=s(n/k) \cdot s(m/k)$$

复杂度的话还好，预处理 $s$ 时可以整出分块，$O(\sqrt{n})$ 爽歪歪。然后的话，发现统计答案的时候 $g$ 函数也可以整出分块，$O(\sqrt{n})$ 。最后总时间复杂度 $O(T\sqrt{n})$ (???) 反正过了就行没超时，时间复杂度我也不会算 $QwQ$ 。

Code:

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>

#define ll long long
#define min(x,y) ((x)<(y)?(x):(y))

const int N=5e4+2;
const int inf=1e9+9;

int T,n,m,cnt;
int mui[N],vis[N],prime[N];
ll s[N]; 

inline void _pre_mui(){
    mui[1]=1;
    for(int i=2;i<=N;++i){
        if(!vis[i])prime[++cnt]=i,mui[i]=-1;
        for(int j=1;j<=cnt;++j){
            if(i*prime[j]>5e4)break;
            vis[i*prime[j]]=1;
            if(!(i%prime[j])){mui[i*prime[j]]=0;break;}
            mui[i*prime[j]]=-mui[i];
        }
    }
    for(int i=1;i<=N;++i)mui[i]+=mui[i-1];
    for(int x=1;x<=N;++x){//实际上这里是 O(n sqrt(n))，不过影响不大。
        ll res=0;
        for(int l=1,r=0;l<=x;l=r+1)
            r=(x/(x/l)),res+=1ll*(r-l+1)*(x/l);
        s[x]=res;
    }return;
}

inline ll solve(int n,int m){
    ll ans=0;
    if(n>m)n^=m^=n^=m;
    for(int l=1,r=0;l<=n;l=r+1){
        r=min(n/(n/l),m/(m/l));
        ans+=1ll*(mui[r]-mui[l-1])*s[n/l]*s[m/l];
    }return ans;
}

int main(){
    _pre_mui();
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        printf("%lld\n",solve(n,m));
    }return 0;
}