【解题报告】[SDOI2015]约数个数和

题目链接

---

要完成这道题，我们首先需要知道关于约数函数 $d(x)$ 的性质，即
$$
d(ij)=\sum_{x|i}\sum_{y|j}[\gcd(x,y)==1]
$$
知道这个性质后，我们就可以愉快的推式子了

---

$$
\begin{align}
&{\bf{设}}\qquad
f(d)=\sum_{i=1}^n\sum_{j=1}^m[\gcd(x,y)==d],F(n)=\sum_{n|d}f(d)
\\
&{\bf{反演得}}\qquad f(n)=\sum_{n|d}\mu(\frac{d}{n})\cdot F(d)
\\
&{\bf{根据 \text{ $d(x)$ }我们得到 }}
\\
&Ans=\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)\\
&{\bf{我们考虑枚举\text{ $d$ },即}}
\\
&Ans=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}\sum_{d}^{\min(n,m)}\mu(d)\cdot [d|\gcd(x,y)]
\\
&=\sum_{d}^{\min(n,m)}\mu(d)\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[d|\gcd(x,y)]
\\
&=\sum_{d}^{\min(n,m)}\mu(d)\sum_{i=1}^n\sum_{j=1}^m [d|\gcd(x,y)]\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor
\\
&=\sum_{d}^{\min(n,m)}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{[\frac{m}{d}\rfloor}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor
\\
&=\sum_{d}^{\min(n,m)}\mu(d){\left(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{i}\rfloor\right)}{\left(\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{m}{j}\rfloor\right)}
\\
\end{align}
$$
得出最终的式子后，我们预处理一下前缀和，就可以用整除分块解决了
$$
\large\color{grey}{\text{Talk is cheap, show you the code}}
$$

inline void get_pre(int n)
{
    mu[1]=1;
    for(register int i=2;i<=n;++i)
    {
        if(!vis[i])
        {
            mu[i]=-1;
            prim[++cnt]=i;
        }
        for(register int j=1;j<=cnt&&i*prim[j]<=n;++j)
        {
            vis[prim[j]*i]=true;
            if(!(i%prim[j]))break;
            mu[prim[j]*i]=-mu[i];
        }
    }
    for(register int i=1;i<=n;++i)g[i]=g[i-1]+mu[i];
    for(register int i=1;i<=n;++i)
    {
        ll res=0;
        for(register int l=1,r;l<=i;l=r+1)
        {
            r=(i/(i/l));
            res+=1ll*(r-l+1)*(i/l);
        }
        sum[i]=res;
    }
}

signed main(void)
{
    T=read();
    get_pre(50000);
    while(T--)
    {
        n=read(),m=read();
        if(n>m)swap(n,m);
        ll ans=0;
        for(register int l=1,r;l<=n;l=r+1)
        {
            r=min(n/(n/l),m/(m/l));
            ans+=1ll*(g[r]-g[l-1])*sum[n/l]*sum[m/l];
        }
        printf("%lld\n",ans);
    }
    return 0;
}