【题目描述】

给定 $n, m$ ,求: $$ \sum_{i = 1}^n\sum_{j = 1}^m [\gcd(i, j) = p], \text{p is prime} $$ $n, m \leq 10^7$ 。

$T$ 组询问,$T \leq 10^4$。

【题目链接】

BZOJ 2820 YY 的 gcd

【解题思路】

$$ \text{ans}(n, m) = \sum_{i = 1}^n \sum_{j = 1}^m[\gcd(i, j) = p], \text{p is prime} $$

枚举质数 $p$ 计算: $$ \text{ans}(n, m) = \sum_{\text{p is prime}}\sum_{i = 1}^n\sum_{j = 1}^m [\gcd(i, j) = p] $$ 考虑到 $\gcd(a, b) = x$ 等价于 $\gcd(\frac a x, \frac b x) = 1$: $$ \text{ans(n, m)} = \sum_{\text{p is prime}} \sum_{i = 1}^n\sum_{j = 1}^m[\gcd(\frac i p, \frac j p) = 1] $$ 改为在枚举 $i' = \frac i p$,$j' = \frac j p$,为方便,仍用 $i, j$ 表示: $$ \text{ans}(n, m) = \sum_{\text{p is prime}} \sum_{i = 1}^{\left \lfloor \frac n p \right \rfloor} \sum_{j = 1}^{\left \lfloor \frac m p \right \rfloor}[\gcd(i, j) = 1] $$ 根据 $[x = 1] = \sum_{d \mid x}\mu(d)$ 即 $\mu \times u = e$ 得: $$ \text{ans}(n, m) = \sum_{\text{p is prime}} \sum_{i = 1}^{\left \lfloor \frac n p \right \rfloor} \sum_{j = 1}^{\left \lfloor \frac m p \right \rfloor}\sum_{d \mid \gcd(i, j)}\mu(d) $$ 更改求和指标,枚举 $d$ ,考虑 $d$ 成为 $\gcd(i, j)$ 因子的次数: $$ \text{ans}(n, m) = \sum_{\text{p is prime}} \sum_d \mu(d) \sum_{i = 1}^{\left \lfloor \frac n p \right \rfloor} \sum_{j = 1}^{\left \lfloor \frac m p \right \rfloor} [d \mid \gcd(i, j)] $$ 类似 BZOJ 1011 中,可以知道后面的两个 $\sum$ 是可以快速计算的: $$ \sum_{i = 1}^{\left \lfloor \frac n p \right \rfloor} \sum_{j = 1}^{\left \lfloor \frac m p \right \rfloor}[d \mid \gcd(i, j)] = \left \lfloor \frac n {pd} \right \rfloor \cdot \left \lfloor \frac m {pd} \right \rfloor $$ 然后: $$ \text{ans}(n, m) = \sum_{\text{p is prime}} \sum_{d} \mu(d)\cdot \left \lfloor \frac n {pd} \right \rfloor \cdot \left \lfloor \frac m {pd} \right \rfloor $$ 设 $T = pd$ ,枚举 $T$,然后枚举 $p$ 作为 $T$ 的质因子,可得: $$ \begin{align*} \text{ans(n, m)} &= \sum_{T}\sum_{\text{p is prime}, p \mid T}\mu(\frac T p) \cdot \left \lfloor \frac n T \right \rfloor \cdot \left \lfloor \frac m T \right \rfloor \\ &= \sum_{T}\left \lfloor \frac n T \right \rfloor \cdot \left \lfloor \frac m T \right \rfloor \cdot \sum_{\text{p is prime}, p \mid T}\mu(\frac T p) \end{align*} $$ 接下来我们的任务就是预处理: $$ f(T) = \sum_{\text{p is prime}, p \mid T} \mu(\frac T p) $$ 法一:先预处理出 $\mu$,然后枚举 $T$ 的质因子累加,总复杂度 $O(n \sqrt n)$。

法二:先预处理出 $\mu$,然后枚举质数 $p$,再枚举 $p$ 的倍数,累加上去。复杂度我不会算,是 $O(n \log n)$或是$O(n \log \log n)$ ?

法三:这个 $f(T)$ 不是积性函数,可我们还是可以线性筛处理它(好霸道)。

1 和质数的情形是容易计算的。根据线性筛的过程,考虑 $x = i \cdot p$ 这样一个合数,分这样两种情况:

当 $p \not \mid i$,首先考虑新来的这个质因子 $p$ 对原来 $i$ 的质因子$p'$贡献的影响,由原来的 $\mu(\frac i {p'})$ 变成了 $\mu(\frac {i \cdot p} {p'} )$ ,多了一个不同的质因子,所以符号反转。然后考虑 $p$ 本身的贡献 $\mu(\frac {i \cdot p} p) = \mu(i)$,所以 $f(i \cdot p) = -f(i) + \mu(i)$。

当 $p \mid i$ ,$\frac {i \cdot p} {p'}$ 中 $p$ 的次数至少为 2,所以 $\mu(\frac {i \cdot p} {p'}) = 0$ ,至于 $p$ 本身,仍然是$\mu(\frac {i \cdot p} {p}) = \mu(i)$ ,所以 $f(i \cdot p) = \mu(i)$ 。

这样预处理出 $f(T)$ 及其前缀和,然后利用下取整除法的性质成块统计答案,就可以在 $O(\sqrt n)$ 的时间回答一次询问了。

总结:线性筛能处理的不只是积性函数。如果函数是积性的, $p \not \mid i$ 的情形可以直接由积性得到,如果没有积性,但仍有一些好的性质可以快速计算这种情形下的函数值,也是可以用线性筛处理的。当然,无论有没有积性,快速计算 $p \mid i$ 都是必要的。

【AC 代码】

#include <cstdio>
#include <algorithm>

typedef long long int64;

const int MAX_N = 10000000;

bool isNotPrime[MAX_N + 1];
int primes[MAX_N + 1], m;
int mu[MAX_N + 1];
int64 f[MAX_N + 1];

inline void sieve(int n = MAX_N){
    isNotPrime[1] = true, mu[1] = 1, f[1] = 0;
    for(int i = 2; i <= n; i++){
        if(!isNotPrime[i]){
            primes[m++] = i;
            mu[i] = -1;
            f[i] = 1;
        }

        for(int j = 0, p, x; j < m; j++){
            if((x = i * (p = primes[j])) > n) break;
            isNotPrime[x] = true;
            if(i % p == 0){
                mu[x] = 0;
                f[x] = mu[i];
                break;
            } else{
                mu[x] = -mu[i];
                f[x] = mu[i] - f[i];
            }
        }
    }

    for(int i = 1; i <= n; i++) f[i] += f[i - 1];
}


int64 solve(int n, int m){
    if(n > m) std::swap(n, m);

    int64 ans = 0;
    for(int l = 1, r; l <= n; l = r + 1){
        r = std::min(n / (n / l), m / (m / l));
        ans += (f[r] - f[l - 1]) * (n / l) * (m / l);
    }
    return ans;
}

int main(){
    sieve();
    
    int T_T;
    scanf("%d", &T_T);
    while(T_T--){
        int n, m;
        scanf("%d%d", &n, &m);

        printf("%lld\n", solve(n, m));
    }

    return 0;
}

就是这样啦~