BZOJ 2820 YY 的 GCD

发表于 | 分类于 |

根据先人总结的 \(\gcd\) 反演题套路，设 \(f(x) = \sum\limits_{i=1}^n \sum\limits_{j=1}^m [\gcd(i,j) = x],F(x) = \sum\limits_{x | i} f(i) = \lfloor \dfrac n x \rfloor \lfloor \dfrac m x \rfloor\)。
那么题目变成了询问 \(\sum\limits_{p \in \mathbb P} f(p)\)，其中 \(\mathbb P\) 表示全体正素数构成的集合。

\[\begin{align*} & \sum\limits_{p \in \mathbb P} f(p) \\ = & \sum\limits_{p \in \mathbb P} \sum\limits_{p | i} \mu(\dfrac i p) F(i) \\ = & \sum\limits_{i = 1}^{\min(n,m)} \sum\limits_{p | i,p \in \mathbb P} \mu(\dfrac i p) \lfloor \dfrac n i \rfloor \lfloor \dfrac m i \rfloor \end{align*}\]

然后预处理 \(sum_i = \sum\limits_{j = 1}^i \sum\limits_{p | j,p \in \mathbb P} \mu(\dfrac j p)\)，对于后面那个东西数论分块即可。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e7;
int t;
int cnt,prime[N + 5],vis[N + 5],mu[N + 5];
long long sum[N + 5];
int main()
{
    mu[1] = 1;
    for(register int i = 2;i <= N;++i)
    {
        if(!vis[i])
            prime[++cnt] = i,mu[i] = -1;
        for(register int j = 1;j <= cnt && i * prime[j] <= N;++j)
        {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j]))
                break;
            else
                mu[i * prime[j]] = -mu[i];
        }
    }
    for(register int i = 1;i <= cnt;++i)
        for(register int j = 1;prime[i] * j <= N;++j)
            sum[prime[i] * j] += mu[j];
    for(register int i = 1;i <= N;++i)
        sum[i] += sum[i - 1];
    scanf("%d",&t);
    int n,m;
    long long ans;
    while(t--)
    {
        ans = 0;
        scanf("%d%d",&n,&m);
        if(n > m)
            swap(n,m);
        for(register int l = 1,r;l <= n;l = r + 1)
        {
            r = min(n / (n / l),m / (m / l));
            ans += (long long)(n / l) * (m / l) * (sum[r] - sum[l - 1]);
        }
        printf("%lld\n",ans);
    }
}