莫比乌斯反演习题：bzoj 2820 YY的GCD

题目描述

有$T$组询问，每次给定$n,m$求$1 \le x \le n \wedge 1 \le y \le m \wedge (x,y) \in P$的$(x,y)$的个数，其中$P$是素数集合

$T = 10000 \wedge n,m \le 10000000$

题解

大力推一波式子吧

$$
\begin{aligned}
n \le m \\
\sum_{p \in P}\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=p]
&=\sum_{p \in P}\sum_{d=1}^{\lfloor \frac{n}{p} \rfloor}\mu(d)\lfloor \frac{n}{pd} \rfloor \lfloor \frac{m}{pd} \rfloor \\
&=\sum_{p \in P}\sum_{T=1 \wedge p \mid T}^{n} \mu(\frac{T}{p}) \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \\
&=\sum_{T=1}^{n} \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{p \in P \wedge p \mid T} \mu(\frac{T}{p}) \\
&=\sum_{T=1}^{n} \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor f(T) \\
f(T)=\sum_{p \in P \wedge p \mid T}\mu(\frac{T}{p})
\end{aligned}
$$

对于每一个$p$，$p \mid T \wedge T \le n$的$T$的取值有$\lfloor \frac{n}{p} \rfloor$种，用每个素数来更新它的倍数的$f$值即可

由于素数定理及调和级数可得知预处理是$O(n+\frac{n}{\log n} \log \frac{n}{\log n})=O(n)$的 实际上是$O(n \log \log n)$的

代码

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N = 10000000 + 10;

int p[N], tot, vis[N], mu[N], n, m;

ll f[N];

void sol() {
    ll ans = 0;
    scanf("%d%d", &n, &m); if(n > m) swap(n, m);
    for(int i = 1, j ; i <= n ; i = j + 1) {
        j = min(n / (n / i), m / (m / i));
        ans += (f[j] - f[i - 1]) * (n / i) * (m / i);
    }
    printf("%lld\n", ans);
}

int main() {
    mu[1] = 1;
    for(int i = 2 ; i <= 10000000 ; ++ i) {
        if(!vis[i]) vis[i] = 1, p[++ tot] = i, mu[i] = -1;
        for(int j = 1 ; j <= tot && (ll) i * p[j] <= 10000000 ; ++ j) {
            vis[i * p[j]] = 1;
            if(i % p[j] == 0) break;
            mu[i * p[j]] = -mu[i];
        }
    }
    for(int i = 1 ; i <= tot ; ++ i)
        for(int j = 1 ; (ll) p[i] * j <= 10000000 ; ++ j)
            f[p[i] * j] += mu[j];
    for(int i = 1 ; i <= 10000000 ; ++ i) f[i] += f[i - 1];
    int T; scanf("%d", &T);
    while(T --) sol();
}