洛谷 P3327 [SDOI2015]约数个数和 题解【莫比乌斯反演】【前缀和】【质因数分解】

点击量：390

有个引理。希望以后这种东西还是能自己推出来

目录

题目描述

设 $d(x)$ 表示 $x$ 的约数个数，给定 $N,M$，求 $\sum^N_{i=1}\sum^M_{j=1}d(ij)$。

输入输出格式

输入格式：

输入文件包含多组测试数据。

第一行，一个整数 $T$，表示测试数据的组数。

接下来的 $T$ 行，每行两个整数 $N,M$。

输出格式：

$T$ 行，每行一个整数，表示你所求的答案。

输入输出样例

输入样例#1：

2
7 4
5 6

输出样例#1：

110
121

说明

$1\le N,M\le 50000$

$1\le T\le 50000​$

题解：

两重循环的和式一般都得推式子来降低复杂度。

当然感觉还得重新做一下 CF1139D Steps to One。

回到这个题，对于 $d(ij)$，我们不知道它有什么性质，只知道 $d=1*1$ 是个积性函数。然而两个 $1$ 函数卷起来并不能给我们的推导带来什么进展。

但是自变量有一个特点，它是两个不超过 $5\times 10^4$ 的数的乘积。

根据唯一分解定理，$ij=p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}$，则 $ij$ 的约数个数是 $\sum_{i=1}^k(c_i+1)$。

设 $i=p_1^{a_1}p_2^{a_2}\cdots p_k^{c_k}$，则 $j=p_1^{c_1-a_1}p_2^{c_2-a_2}\cdots p_k^{c_k-a_k}$。令 $x|i$，$y|j$，有 $x=p_1^{b_1}p_2^{b_2}\cdots p_k^{b_k}$，其中 $\forall i\in [1,k]$，$b_i\le a_i$，同理 $y=p_1^{t_1}p_2^{t_2}\cdots p_k^{t_k}$，$t_i\le c_i-a_i$。

可知 $b_i$ 有 $a_i+1$ 种取值，$t_i$ 有 $c_i-a_i+1$ 种取值。如果把它们相加，就出现了 $c_i+2$。

此时我们针对 $b_i$ 和 $t_i$ 的这些取值，构造 $\gcd(x,y)=1$，这样就可以满足 $\forall i\in[1,k]$，$b_i=0\lor t_i=0$。满足 $b_i=0\lor t_i=0$ 的情况就是 $c_i+1$ 种了。因此 $d(ij)=\sum_{i=1}^k(c_i+1)=\sum_{x|i}\sum_{y|j}[\gcd(i,j)=1]$。

我们要求的答案是
$$
\sum_{i=1}^n\sum_{i=1}^md(ij)=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[\gcd(x,y)=1]
$$
根据反演的套路，令
$$
f(k)=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[\gcd(x,y)=n]\\
\begin{aligned}
g(k)&=\sum_{k|d}f(d)\\
&=\sum_{k|d}\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[\gcd(x,y)=d]\\
&=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[k|\gcd(x,y)]\\
&=\sum_{i=1}^\left\lfloor\frac nk\right\rfloor\sum_{j=1}^\left\lfloor\frac mk\right\rfloor\sum_{x|i}\sum_{y|j}[1|\gcd(x,y)]\\
&=\sum_{i=1}^\left\lfloor\frac nk\right\rfloor\sum_{j=1}^\left\lfloor\frac mk\right\rfloor d(i)d(j)
\end{aligned}
$$
由于 $d$ 是积性函数 $i,j\le 5\times 10^4$，所以可以在 $O(n)$ 的时间内筛出来。

因为每个数 $x$ 会被最小的质因子 $p$ 和自然数 $\frac xp$ 筛出来，如果 $\frac xp$ 有 $p$ 这个质因子，那么在线筛中 $p$ 一定是 $\frac xp$ 的最小质因子，此时 $d(x)=\frac{d\left(\frac xp\right)}{c_p+1}\times (c_p+2)$。其中 $c_p$ 是 $\frac xp$ 质因数分解后 $p$ 这个因子的幂。

而每个数只有最小质因子有用，所以只用把它存下来就可以了。

如果 $\frac xp$ 没有 $p$ 这个质因子，则 $\frac xp$ 和 $p$ 互质，$d(x)=d\left(\frac xp \right)d(p)$。

时间复杂度 $O\left(T\sqrt n\right)$（假定 $n$，$m$ 同阶）。

Code：

#include<cstdio>
#include<cstring>
#define ll long long
int Min(int x,int y){return x<y?x:y;}
int read()
{
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x;
}
bool is[50010];
int pri[10000],f[50010],cnt=0;
ll mu[50010],d[50010];
int main()
{
    is[0]=is[1]=1;
    mu[1]=1,d[1]=1;
    for(int i=2;i<=50000;++i)
    {
        if(!is[i])
        {
            pri[++cnt]=i;
            mu[i]=-1;
            d[i]=2;
            f[i]=2;
        }
        for(int j=1;j<=cnt&&i*pri[j]<=50000;++j)
        {
            is[i*pri[j]]=1;
            if(i%pri[j])
            {
                mu[i*pri[j]]=-mu[i];
                f[i*pri[j]]=2;
                d[i*pri[j]]=2*d[i];
            }
            else
            {
                mu[i*pri[j]]=0;
                f[i*pri[j]]=f[i]+1;
                d[i*pri[j]]=d[i]/f[i]*f[i*pri[j]];
                break;
            }
        }
        d[i]+=d[i-1];
        mu[i]+=mu[i-1];
    }
    int T=read(),a,b;
    while(T--)
    {
        a=read();
        b=read();
        if(a>b)
        {
            int t=a;
            a=b;
            b=t;
        }
        ll ans=0;
        for(int i=1;i<=a;++i)
        {
            int nxt=Min(Min(a/(a/i),b/(b/i)),a);
            ans+=(mu[nxt]-mu[i-1])*d[a/i]*d[b/i];
            i=nxt;
        }
        printf("%lld\n",ans);
    }
    return 0;
}