[SDOI2015]约数个数和

题解

---

前言

首先感谢yyb的题解让我大概懂了做法
然后感谢syc的讲解让我明白的关键要点

正文

$Mobius$反演的题,从yyb那里看下大概流程，然后这里讲两个地方

Part 1 推式子

$$\sum_{i=1}^{N}\sum_{j=1}^{M}d(ij)=\sum_{i=1}^{N}\sum_{j=1}^{M}\sum_{u|i}\sum_{v|j}gcd(i,j)==1$$
原理请见这篇文章章末引理$B$
$$=\sum_{u=1}^{N}\sum_{v=1}^{M}[gcd(u,v)==1]\lfloor\frac{N}{u}\rfloor\lfloor\frac{M}{v}\rfloor$$
把外面的贡献提出来，那么每个$u$会被枚举到$\lfloor\frac{N}{u}\rfloor$次，同理计算$v$
$$=\sum_{d=1}^{N}\mu(d)\sum_{i=1}^{\lfloor\frac{N}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{d}\rfloor}\lfloor\frac{N}{id}\rfloor\lfloor\frac{M}{jd}\rfloor$$
请自行$Mobius$反演，不会可以看yyb的博客，但最后一句写错了，是$\lfloor\frac{M}{jd}\rfloor$

解决后面这一坨

$$\sum_{i=1}^{\lfloor\frac{N}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{d}\rfloor}\lfloor\frac{N}{id}\rfloor\lfloor\frac{M}{jd}\rfloor$$
其实相当于这个($\lfloor{\frac{\frac{n}{i}}{d}}\rfloor=\lfloor{\frac{n}{id}}\rfloor$可以见刚才那篇文章的引理$A$)，用$n$代替$\lfloor\frac{N}{i}\rfloor$
$$\sum_{i=1}^{n}\sum_{j=1}^{m}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor$$
然后运用乘法分配率
$$(\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor)(\sum_{j=1}^{m}\lfloor\frac{m}{j}\rfloor)$$
那么只需要对这个式子处理就好了
$$\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor$$
上式可以表示枚举一个因子$i$，那么$[1,n]$中有$\lfloor\frac{n}{i}\rfloor$个数含有因子$i$，枚举完$[1,n]$中所有的因子然后累加，可以说是求$[1,n]$中每个数的因子个数和吧，即
$$\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor=\sum_{i=1}^{n}d(i)$$

Part 2 线性筛$d(i)$

一个数唯一分解为$x=p_1^{a_1}p_2^{a_1}……p_k^{a_k}$，则

$$d(x)=\prod_{i=1}^{k}(a_i+1)$$
原理是枚举每个质因子选$0$到$a_i$个
我们可以知道一个数的约数个数函数是积性函数
所以可以线性筛，又和其他自定义的积性函数筛法略微不同
用$d[i]$表示$i$的因数个数，用$p[i]$表示$i$唯一分解后最小质因子的次数
代码如下慢慢体会

inline void Sieve()
{
    ispri[1]=1;p[1]=1;d[1]=1;
    for(RG int i=2;i<=MAXN;i++)
    {
        if(!ispri[i]){pri[++tot]=i;p[i]=1;d[i]=2;}
        for(RG int j=1;j<=tot&&i*pri[j]<=MAXN;j++)
        {
            ispri[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                d[i*pri[j]]=d[i]/(p[i]+1)*(p[i]+2);//d[i]表示i的因数个数
                p[i*pri[j]]=p[i]+1;//p[i]表示i唯一分解后最小质因子的次数
                break;
            }
            d[i*pri[j]]=d[i]*d[pri[j]];//实际上就是d[i]*2
            p[i*pri[j]]=1;
        }
    }
}

这样子$O(n)$预处理，$O(\sqrt{n})$处理询问，总复杂度$O(n+T\sqrt{n})$

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define RG register 
#define ll long long
using namespace std;
inline int read()
{
    RG char ch=getchar();
    RG int h=0;
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();}
    return h;
}
const int MAXN=50000;
int mu[MAXN+1],pri[MAXN>>1],tot;
int p[MAXN+1],d[MAXN+1],s[MAXN+1],sd[MAXN+1];
bool ispri[MAXN+1];
inline void Mobius()
{
    mu[1]=1;ispri[1]=1;p[1]=1;d[1]=1;
    for(RG int i=2;i<=MAXN;i++)
    {
        if(!ispri[i]){pri[++tot]=i;p[i]=1;mu[i]=-1;d[i]=2;}
        for(RG int j=1;j<=tot&&i*pri[j]<=MAXN;j++)
        {
            ispri[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                //mu[i*pri[j]]=0;//卡常
                d[i*pri[j]]=d[i]/(p[i]+1)*(p[i]+2);//d[i]表示i的因数个数
                p[i*pri[j]]=p[i]+1;//p[i]表示i唯一分解后最小质因子的次数
                break;
            }
            mu[i*pri[j]]=-mu[i];
            d[i*pri[j]]=d[i]*d[pri[j]];//实际上就是d[i]*2
            p[i*pri[j]]=1;
        }
    }
    for(RG int i=1;i<=MAXN;i++)s[i]=s[i-1]+mu[i];
    for(RG int i=1;i<=MAXN;i++)sd[i]=sd[i-1]+d[i];
}
int main()
{
    RG int T=read();Mobius();
    while(T--)
    {
        RG int N=read(),M=read();
        if(N>M)swap(N,M);
        RG int l=1,r;RG ll ans=0;
        while(l<=N)
        {
            r=min(N/(N/l),M/(M/l));
            ans+=1LL*(s[r]-s[l-1])*sd[N/l]*sd[M/l];
            l=r+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}