一句话题意：
求出 (displaystylesum_{i=1}^{n}sum_{j=1}^{m} au(i) au(j) au(gcd(i,j)))
前置知识
-
(dirirchlet) 卷积
这里我们只需要了解他的一个性质， ( au * mu = epsilon), 具体证明如下：
( au = 1 * 1)
(epsilon = mu * 1)
对于第一个柿子，两边同时卷上一个 (mu) 变成：
( au * mu = 1 * 1 * mu)
( au * mu = 1 * epsilon = 1)
2.线性筛约数个数
首先，我们对一个数有唯一分解定理：(p = p_1^{k_1} imes 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 imes p) 的时候筛到他。
若 (i mod p == 0) 表明 (p) 是 (n) 的最小质因子 ，则有 (g[n] = 1), (f[n] =) (f[i] imes (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:
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) 来变成：
(displaystylesum_{d=1}^{n} au(d) sum_{i=1}^{n} sum_{j=1}^{m} au(i) au(j)[gcd(i,j) == d])
后面那两个求和柿子可以提出一个 (d) 出来变成：
(displaystylesum_{d=1}^{n} au(d) sum_{i=1}^{nover d} sum_{j=1}^{mover d} au(i imes d) au(j imes d)[gcd(i,j) == 1])
根据莫比乌斯反演，我们可以得到一个等式：
([gc(i,j) == 1] = displaystylesum_{pmid i,pmid j} mu(p))
把这个等式代回原式有：
(displaystylesum_{d=1}^{n} au(d)sum_{i=1}^{nover d}sum_{j=1}^{m over d} au(i imes d) au(j imes d) sum_{pmid i pmid j} mu(p))
先枚举一下 (p) 变成：
(displaystylesum_{d=1}^{n} au(d)sum_{p=1}^{nover d} mu(p)sum_{i=1}^{nover d} au(i imes d)[p mid i]sum_{j=1}^{m over d} au(j imes d) [p mid j])
后面的那个求和柿子可以变成：
(displaystylesum_{d=1}^{n} au(d)sum_{p=1}^{nover d} mu(p)sum_{i=1}^{nover {dp}} au(i imes d p) sum_{j=1}^{m over {dp}} au(j imes dp))
设 (Q = dp) 则 (p = {Q over d}),柿子可以写成：
(displaystylesum_{d=1}^{n} au(d)sum_{Q=1}^{n}mu({Qover d})sum_{i=1}^{nover Q}sum_{j = 1}^{m over Q} au(iQ) au(jQ))
改变一下枚举顺序，先枚举一下 (Q) 则有：
(displaystylesum_{Q=1}^{n}sum_{dmid Q}^{n} au(d)mu({Qover d})sum_{i=1}^{nover Q}sum_{j=1}^{mover Q} au(iQ) au(jQ))
中间的这个 (displaystylesum_{dmid Q}^{n} au(d)mu({Qover d})) 柿子，利用我们前置知识里的一个性质：( au * mu = 1) 也就是这个柿子恒等于 (1)
我们的柿子就可以变为：
(displaystylesum_{Q=1}^{n}sum_{i=1}^{nover Q}sum_{j=1}^{mover Q} au(iQ) au(jQ))
这个直接枚举的复杂度跟定会爆的，我们还要考虑优化。
我们可以对于每个 (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
",slove(n,m));
return 0;
}
话说，这题感觉难度有点低，应该是紫题吧，毕竟最后的 (dirilect) 后缀和优化的模板题都是紫的