题解 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. 这里我们只需要了解他的一个性质， $\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

Code:

    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 来变成：

后面那两个求和柿子可以提出一个 d 出来变成：

根据莫比乌斯反演，我们可以得到一个等式：

把这个等式代回原式有：

先枚举一下 p 变成：

后面的那个求和柿子可以变成：

设 Q = dp 则 p = {Q \over d},柿子可以写成：

改变一下枚举顺序，先枚举一下 Q 则有：

中间的这个 \displaystyle\sum_{d\mid Q}^{n}\tau(d)\mu({Q\over d}) 柿子，利用我们前置知识里的一个性质：\tau * \mu = 1 也就是这个柿子恒等于 1

我们的柿子就可以变为：

这个直接枚举的复杂度跟定会爆的，我们还要考虑优化。

我们可以对于每个 Q 先把他后面的两个柿子先预处理出来，之后我们在枚举每个 Q 时可以直接得到这个 Q 的·贡献。

据说还可以用 dirichlet 后缀和优化，然鹅我并不会。

Code

#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 后缀和优化的模板也是紫的。