题解 P6810 【「MCOI-02」Convex Hull 凸包】
genshy
2020-09-15 09:23:41
### 一句话题意：
求出 $\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{m}\tau(i)\tau(j)\tau(gcd(i,j))$
### 前置知识
1. $dirirchlet$ 卷积
这里我们只需要了解他的一个性质， $\tau * \mu = \epsilon$, 具体证明如下：
> $\tau = 1 * 1$，
> $\epsilon = \mu * 1$
>
> 对于第一个柿子，两边同时卷上一个 $\mu$ 变成：
>
> $\tau * \mu = 1 * 1 * \mu$
>
> $\tau * \mu = 1 * \epsilon = 1$
2.线性筛约数个数
首先，我们对一个数有唯一分解定理：$p = p_1^{k_1} \times p_2^{k2} \cdots p_n ^{kn}$
那么这个数的约数个数可以写为 $\prod (k_i+1)$ ~~(这小学知识啦~~)。
我们维护两个数组 $g[i]$ 表示 $i$ 的最小质因子的次数， $t[i]$ 表示 $i$ 的约数个数和。
对于 质数 $p$ 则有 $g[p] = 1, t[p] = 2$
对于不是质数的数 $n$ 我们在筛的时候会在 $i \times p$ 的时候筛到他。
若 $i \bmod p == 0$ 表明 $p$ 是 $n$ 的最小质因子 ，
则有 $g[n] = 1$, $f[n] =$ $f[i] \times (g[n]+1) \over {g[i]+1}$
若 $i 和 p 互质$ 可以利用积性函数的性质求解，则有 $g[n] = g[i] + 1$
$f[n] = f[i] * f[p]$ ， 也可以写成 $f[n] = f[i] * 2$
**Code**:
```cpp
g[1] = 1; t[1] = 1;
for(int i = 2; i <= N-5; i++)
{
if(!check[i])
{
prime[++tot] = i;
g[i] = 1;
t[i] = 2;
}
for(int j = 1; j <= tot && i * prime[j] <= N-5; j++)
{
check[i * prime[j]] = 1;
if(i % prime[j] == 0)
{
g[i * prime[j]] = g[i] + 1;
t[i * prime[j]] = t[i] * (g[i * prime[j]] + 1) / (g[i] + 1);
break;
}
else
{
g[i * prime[j]] = 1;
t[i * prime[j]] = t[i] * t[prime[j]];
}
}
}
```
### **题解**
比较难的懵逼乌斯反演题。
首先，我们还是按照套路先枚举一个 $d$ 来变成：
$\displaystyle\sum_{d=1}^{n}\tau(d) \sum_{i=1}^{n} \sum_{j=1}^{m}\tau(i)\tau(j)[gcd(i,j) == d]$
后面那两个求和柿子可以提出一个 $d$ 出来变成：
$\displaystyle\sum_{d=1}^{n}\tau(d) \sum_{i=1}^{n\over d} \sum_{j=1}^{m\over d}\tau(i \times d)\tau(j \times d)[gcd(i,j) == 1]$
根据莫比乌斯反演，我们可以得到一个等式：
$[gc(i,j) == 1] = \displaystyle\sum_{p\mid i,p\mid j} \mu(p)$
把这个等式代回原式有：
$\displaystyle\sum_{d=1}^{n}\tau(d)\sum_{i=1}^{n\over d}\sum_{j=1}^{m \over d}\tau(i \times d)\tau(j\times d) \sum_{p\mid i p\mid j} \mu(p)$
先枚举一下 $p$ 变成：
$\displaystyle\sum_{d=1}^{n}\tau(d)\sum_{p=1}^{n\over d} \mu(p)\sum_{i=1}^{n\over d} \tau(i \times d)[p \mid i]\sum_{j=1}^{m \over d}\tau(j \times d) [p \mid j]$
后面的那个求和柿子可以变成：
$\displaystyle\sum_{d=1}^{n}\tau(d)\sum_{p=1}^{n\over d} \mu(p)\sum_{i=1}^{n\over {dp}} \tau(i \times d p) \sum_{j=1}^{m \over {dp}}\tau(j \times dp)$
设 $Q = dp$ 则 $p = {Q \over d}$,柿子可以写成：
$\displaystyle\sum_{d=1}^{n}\tau(d)\sum_{Q=1}^{n}\mu({Q\over d})\sum_{i=1}^{n\over Q}\sum_{j = 1}^{m \over Q}\tau(iQ)\tau(jQ)$
改变一下枚举顺序，先枚举一下 $Q$ 则有：
$\displaystyle\sum_{Q=1}^{n}\sum_{d\mid Q}^{n} \tau(d)\mu({Q\over d})\sum_{i=1}^{n\over Q}\sum_{j=1}^{m\over Q}\tau(iQ)\tau(jQ)$
中间的这个 $\displaystyle\sum_{d\mid Q}^{n}\tau(d)\mu({Q\over d})$ 柿子，利用我们前置知识里的一个性质：$\tau * \mu = 1$ 也就是这个柿子恒等于 $1$
我们的柿子就可以变为：
$\displaystyle\sum_{Q=1}^{n}\sum_{i=1}^{n\over Q}\sum_{j=1}^{m\over Q} \tau(iQ)\tau(jQ)$
这个直接枚举的复杂度跟定会爆的，我们还要考虑优化。
我们可以对于每个 $Q$ 先把他后面的两个柿子先预处理出来，之后我们在枚举每个 $Q$ 时可以直接得到这个 $Q$ 的·贡献。
据说还可以用 $dirichlet$ 后缀和优化，然鹅我并不会。
**Code**
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 2e6+10;
int n,m,p,tot;
int t[N],g[N],prime[N],sum1[N],sum2[N];
bool check[N];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s =s * 10+ch - '0'; ch = getchar();}
return s * w;
}
void YYCH()
{
g[1] = 1; t[1] = 1;
for(int i = 2; i <= N-5; i++)//预处理出每个数的约数个数
{
if(!check[i])
{
prime[++tot] = i;
g[i] = 1;
t[i] = 2;
}
for(int j = 1; j <= tot && i * prime[j] <= N-5; j++)
{
check[i * prime[j]] = 1;
if(i % prime[j] == 0)
{
g[i * prime[j]] = g[i] + 1;
t[i * prime[j]] = t[i] * (g[i * prime[j]] + 1) / (g[i] + 1);
break;
}
else
{
g[i * prime[j]] = 1;
t[i * prime[j]] = t[i] * t[prime[j]];
}
}
}
}
int slove(int n,int m)
{
YYCH();
int res = 0;
for(int d = 1; d <= n; d++)//预处理出每个 Q 的贡献
{
for(int j = 1; j <= n/d; j++)
{
sum1[d] = (sum1[d] + t[j * d]) % p;
}
}
for(int d = 1; d <= m; d++)
{
for(int j = 1; j <= m/d; j++)
{
sum2[d] = (sum2[d] + t[j * d]) % p;
}
}
for(int d = 1; d <= n; d++)//枚举每个Q
{
res = (res + 1LL * sum1[d] * sum2[d] % p) % p;//计算答案
}
return res % p;
}
int main()
{
n = read(); m = read(); p = read();
if(n > m) swap(n,m);
printf("%d\n",slove(n,m));
return 0;
}
```
话说，这题感觉难度有点低，应该是紫题吧，毕竟最后的 $dirichlet$ 后缀和优化的模板也是紫的。