【题目描述】
给定 $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;
}
就是这样啦～