约数个数和 SDOI2015

WZH2026-09-122026-09-12

[SDOI2015] 约数个数和

第一步可参考第一篇题解。

\sum_{i \le n}\sum_{j \le m}d(ij)

=\sum_{i \le n}\sum_{j \le m}\sum_{k \mid i}\sum_{l \mid j}[(k,l)=1]

=\sum_{i \le n}\sum_{ k \mid i}\sum_{j \le m}\sum_{l\mid j}[(k,l)=1]

由于枚举 $i \le n$ ，再枚举 $i$ 的因数，等价于先枚举 $i \le n$ ，再枚举 $i$ 的倍数， $j$ 同理。而 $i$ 的倍数有 $\lfloor \frac{n}{i} \rfloor$ 个， $j$ 同理，所于原式等价于：

\sum_{i \le n}\lfloor\frac{n}{i}\rfloor\sum_{j \le m}\lfloor\frac{m}{j}\rfloor[(i,j)=1]

=\sum_{i \le n}\sum_{j \le m}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor[(i,j)=1]

=\sum_{i \le n} \sum_{j \le m}\sum_{d \mid (i,j)}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor\mu(d)

=\sum_{i \le n}\sum_{j \le m}\sum_{d\mid i}\sum_{d \mid j}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor\mu(d)

=\sum_{i \le n}\sum_{d \mid i}\sum_{j \le m}\sum_{d \mid j}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor\mu(d)

同上理，原式等价于：

\sum_{d\le n}\sum_{d \mid i}\sum_{d\le j}\sum_{d \mid j}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor\mu(d)

=\sum_{d \le \min(n,m)}{\mu(d)\sum_{d \mid i}\sum_{d \mid j}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor}

由于上式中 $i,j$ 均为 $d$ 的倍数，所以原式可简化为：

\sum_{d \le \min(n,m)}{\mu(d)\sum_{i \le \lfloor\frac{n}{d}\rfloor}\sum_{j \le \lfloor\frac{m}{d}\rfloor}\lfloor\frac{\lfloor\frac{n}{d}\rfloor}{i}\rfloor\lfloor\frac{\lfloor\frac{m}{d}\rfloor}{j}\rfloor}

设 $nn=\lfloor\frac{n}{d}\rfloor,mm=\lfloor\frac{m}{d}\rfloor$ ，发现上式中， $nn,mm$ 仅与 $d$ 有关，且 $nn,mm$ 为向下取整的除法形式，可以使用整除分块，不会的跳转 [CQOI2007] 余数求和。

这样复杂度便来到了 $O(Tn^2\sqrt{n})$ ，可以通过 $50\%$ 的数据。

又因为上述求和式子内部为整除分块模板的二维形式，可以考虑依次简化。先套用模板解决内部 $j$ 的求和，设答案为 $res_1$ ，则将其带入，式子为：

\sum_{i \le nn} \lfloor\frac{nn}{i}\rfloor \times res_1=res_1\times\sum_{i \le nn} \lfloor\frac{nn}{i}\rfloor

此时关于 $i$ 的求和也为整除分块模板，也使用整除分块化简，最终复杂度就是 $O(Tn\sqrt{n})$ ，可以通过 $70\%$ 的数据。

然后，注意到对 $i$ 和 $j$ 的整除分块一样，且对于任意的 $nn,mm$ ，都有对 $i$ 和 $j$ 的整除分块一样。所以可以考虑 $O(n\sqrt{n})$ 的预处理处理出所有的：

\sum_{i \le n} \lfloor\frac{n}{i}\rfloor

这样就可以做到 $O(n\sqrt{n}+T\sqrt{n})$ 的复杂度了，可以通过 $100\%$ 的数据。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=50010;
int p[N],cnt,book[N],mu[N],n,m,sum[N];
long long smm[N];
void get_prime(int x){
    mu[1]=1;
    for(int i=2;i<=x;i++){
        if(!book[i])p[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt&&i*p[j]<=x;j++){
            book[i*p[j]]=1;
            if(i%p[j]==0)break;
            mu[i*p[j]]=-mu[i];
        }
    }
    for(int i=1;i<=x;i++)sum[i]=sum[i-1]+mu[i];
}
int minh(int a,int b){return a<b?a:b;}
int main(){
    int T;
    scanf("%d",&T);
    get_prime(50000);
    for(int i=1;i<=50000;i++){
        for(int l=1,r;l<=i;l=r+1){
            r=minh(i,i/(i/l));
            smm[i]+=(i/l)*(r-l+1);
        }
    }
    while(T--){
        scanf("%d%d",&n,&m);
        long long ans=0;
        int mn=minh(n,m);
        for(int l=1,r;l<=mn;l=r+1){
            r=minh(mn,minh(n/(n/l),m/(m/l)));
            ans+=smm[m/l]*smm[n/l]*(sum[r]-sum[l-1]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}