[题解] Luogu – 2247 YY的GCD

题目描述

给定 $N$ 和 $M$，求 $1 \leq x \leq N$，$1 \leq y \leq M$ 且 $gcd(x, y)$ 为质数的 $(x, y)$ 有多少对

本题有多组输入

输入格式

第一行一个整数 $T$ 表示数据组数
接下来 $T$ 行，每行两个正整数，表示 $N$ 和 $M$

输出格式

$T$ 行，每行一个整数表示第 $i$ 组数据的结果

样例输入

2
10 10
100 100

样例输出

30
2791

数据范围及约定

对于 $100 \%$ 的数据，$T = 10000$，$N, M \leq 10^7$
时间限制: 4s
空间限制: 512MB

解题思路

本题即为求解

$$
\sum_{i=1}^n \sum_{j=1}^m \boldsymbol{f}(gcd(i, j))
$$

令 $\boldsymbol{f}(x)$ 为

$$
\boldsymbol{f}(x) =
\begin{cases}
1 & n 是质数 \\
0 & n 不是质数
\end{cases}
$$

考虑构造一个数论函数 $\boldsymbol{g}(x)$ 使得
$$
\boldsymbol{f} = \boldsymbol{1} * \boldsymbol{g}
$$

那么

$$
\boldsymbol{g} = \boldsymbol{\mu} * \boldsymbol{f}
$$

即

$$
\boldsymbol{g}(n) = \sum_{p \mid n} \boldsymbol{\mu}(\frac{x}{n})
$$

这个函数可以在 $O(n \log \log n)$ 的时间内筛出来

原始等价于求

$$
\sum_{i=1}^n \sum_{j=1}^n \sum_{d \mid gcd(i, j)} \boldsymbol{g}(d)
$$

因为 $d \mid gcd(i, j)$ 等价于 $d \mid i, d \mid j$

$$
\begin{aligned}
& \sum_{i=1}^n \sum_{i=1}^m \sum_{d \mid i, d \mid j} \boldsymbol{g}(d) \\
& = \sum_{d=1}^{\min(n, m)} \boldsymbol{g}(d) \sum_{i=1}^n \sum_{j=1}^m [d \mid i] [d \mid j] \\
& = \sum_{d=1}^{\min(n, m)} \boldsymbol{g}(d) \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor
\end{aligned}
$$

考虑对 $\boldsymbol{g}(n)$ 求一个前缀和，使用数论分块即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 10000000 + 10;
const int SIZ = 10000000;

inline int read(){
    int x = 0;
    char ch = getchar();

    while(ch < '0' || ch > '9')
        ch = getchar();

    while('0' <= ch && ch <= '9'){
        x = x*10 + ch - '0';
        ch = getchar();
    }

    return x;
}

int mu[MAXN], prime[MAXN], g[MAXN], cnt;
long long sum[MAXN];

bool isPrime[MAXN];

inline void init(){
    mu[1] = 1;
    for(register int i=2; i<=SIZ; i++){
        if(!isPrime[i]){
            prime[++cnt] = i;
            mu[i] = -1;
        }

        for(register int j=1; j<=cnt; j++){
            if(i * prime[j] > SIZ)
                break;

            isPrime[i * prime[j]] = true;

            if(i % prime[j] == 0){
                mu[i * prime[j]] = 0;
                break;
            }else{
                mu[i * prime[j]] = -mu[i];
            }
        }
    }

    for(register int i=1; i<=cnt; i++){
        int p = prime[i];
        for(register int j=1; j * p <= SIZ; j++){
            g[j * p] += mu[j];
        }
    }

    for(register int i=1; i<=SIZ; i++){
        sum[i] = sum[i-1] + g[i];
    }
}

long long ans;

inline void solve(int n, int m){
    ans = 0;
    for(register int i=1, j; i<=min(n, m); i = j + 1){
        j = min(n/(n/i), m/(m/i));
        ans += 1LL * (n/i) * (m / i) * (sum[j] - sum[i-1]);
    }
}

int T, n, m;

int main(){
    init();

    T = read();

    while(T--){
        n = read();
        m = read();

        solve(n, m);

        printf("%lld\n", ans);
    }

    return 0;
}