题目描述

有$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)$的

代码

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
#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();
}