BZOJ3994【SDOI2015】约数个数和 <莫比乌斯反演>

Problem

【SDOI2015】约数个数和

$\mathrm{Time\;Limit:\;20\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

设$d(x)$为$x$的约数个数，给定$N,M$，求$\sum_{i=1}^{n}\sum_{j=1}^{m}d(i\cdot j)$

Input

输入文件包含多组测试数据。
第一行，一个整数$T$，表示测试数据的组数。
接下来的$T$行，每行两个整数$N,M$。

Output

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

Sample Input

2
7 4
5 6

Sample Output

110
121

HINT

$1\le N,M\le50000,\;1\le T\le50000$

标签：莫比乌斯反演

Solution

挺神的反演，没推出来，需要一个结论。

首先考虑如何把$d(x)$变为我们更为熟悉的数学语言。
对于$d(x\cdot y)$，考虑$x\times y$的约数，每个约数均可表示为$i\times \frac{y}{j}$，其中$i|x,j|y$。那么用$\sum_{i|x}\sum_{j|y}1$统计约数，一定会不漏地枚举到所有约数，但显然是有重复的。注意到这种重复的造成只有一种情况，即若$(i,j)$符合条件，那么$(i\times t,j\times t)$也符合条件，而两者所代表的最终约数是相同的，重复计数。也就是说只要$\gcd(i,j)\ne1$，那么一定是重复计算的。于是不重不漏地计算只需要把$\sum_{i|x}\sum_{j|y}1$中的$1$加上$\gcd(i,j)=1$的限制即可。
因此推出重要结论$d(x\cdot y)=\sum_{i|x}\sum_{j|y}[\gcd(i,j)=1]$。

接下来就可以推反演了：

$$\begin{aligned} Ans&=\sum_{k=1}^{n}\sum_{w=1}^{m}d(k\cdot w)\\ &=\sum_{k=1}^{n}\sum_{w=1}^{m}\sum_{i|k}\sum_{j|w}[\gcd(i,j)=1]\\ &=\sum_{i=1}^{n}\sum_{j=1}^{m}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor[\gcd(i,j)=1]\\ &=\sum_{i=1}^{n}\sum_{j=1}^{m}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor\sum_{d|i,d|j}\mu(d)\\ &=\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{\lfloor n/d\rfloor}\sum_{j=1}^{\lfloor m/d\rfloor}\lfloor\frac{n}{i\cdot d}\rfloor\lfloor\frac{m}{j\cdot d}\rfloor\\ &=\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{\lfloor n/d\rfloor}\lfloor\frac{n}{i\cdot d}\rfloor\sum_{j=1}^{\lfloor m/d\rfloor}\lfloor\frac{m}{j\cdot d}\rfloor\\ \end{aligned}$$

如果能预处理出$F(x)=\sum_{i=1}^{x}\lfloor\frac{x}{i}\rfloor$的值，就可以根号分块计算答案。

考虑$\sum_{i=1}^{x}\lfloor\frac{x}{i}\rfloor​$的意义，即枚举一个数，统计其在$[1,x]​$内的倍数有多少个，可以理解为枚举约数，计算它在$1\sim x​$中是多少个数的约数，即计算其对$\sum_{i=1}^{x}d(i)​$的贡献。于是$F(x)=\sum_{i=1}^{x}d(i)​$，我们需要预处理出$d(x)​$。

由于$d(x)$是积性函数，对于$d(x\cdot p)\;(x\in \mathbb{N}^*,\;p<x,\;p是质数)$，我们有：

1. $p\nmid x$：$d(x\cdot p)=d(x)\cdot d(p)$
2. $p\mid x$：$d(x\cdot p)=d(\frac{x}{p^k}\cdot p^{k+1})=d(\frac{x}{p^k})\cdot d(p^{k+1})=\frac{d(x)\cdot(k+2)}{k+1}$，其中$p$一定为$x$的最小质因子

为了应对情况$2$，我们需要预处理最小质因子次数$c(x)$，注意到$c(x)$也可以线性筛预处理：

1. 对于质数$p$，$c(p)=1$
2. 对于正整数$x$和质数$p$，

• $p\nmid x$：$c(x\cdot p)=1$
• $p\mid x$：$c(x\cdot p)=c(x)+1$

如此我们即可线性筛预处理出$c(x),\;d(x)$，计算$d(x)$前缀和$F(x)$，对于询问进行数论分块统计答案，时间复杂度$O(T\sqrt{n})$。

Code

#include <bits/stdc++.h>
#define MAX_N 50000
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
bool NotPri[MAX_N+5]; int pri[MAX_N+5], cnt;
lnt mu[MAX_N+5], c[MAX_N+5], d[MAX_N+5], ans;
void init() {
    mu[1] = 1, d[1] = 1;
    for (int i = 2; i <= MAX_N; i++) {
        if (!NotPri[i]) pri[cnt++] = i, mu[i] = -1, c[i] = 1, d[i] = 2;
        for (int j = 0; j < cnt; j++) {
            if (i*pri[j] > MAX_N) break;	NotPri[i*pri[j]] = true;
            if (i%pri[j]) mu[i*pri[j]] = -mu[i], c[i*pri[j]] = 1, d[i*pri[j]] = d[i]*d[pri[j]];
            else mu[i*pri[j]] = 0, c[i*pri[j]] = c[i]+1, d[i*pri[j]] = d[i]*(c[i]+2)/(c[i]+1);
            if (i%pri[j] == 0) break;
        }
    }
    for (int i = 2; i <= MAX_N; i++) mu[i] += mu[i-1], d[i] += d[i-1];
}
int main() {
    int n, m, T; read(T), init();
    while (T--) {
        read(n), read(m), ans = 0;
        for (int l = 1, r; l <= min(n, m); l = r+1)
            r = min(n/(n/l), m/(m/l)), 
            ans += (mu[r]-mu[l-1])*d[n/l]*d[m/l];
        printf("%lld\n", ans);
    }
    return 0;
}