「BZOJ2820」YY的GCD

Description

给定NN, MM,求1xN1\leq x\leq N, 1yM1\leq y\leq Mgcd(x,y)gcd(x, y)为质数的(x,y)(x, y)有多少对。

Input

第一行一个整数TT表述数据组数接下来TT行,每行两个正整数,表示NN,MM

Output

TT行,每行一个整数表示第ii组数据的结果

HINT

T=10000T=10000
N,M10000000N,M\leq10000000

Solution

这题和「BZOJ2301」类似。
定义:
F(p)F(p)表示pgcd(x,y)p|gcd(x,y)的点对个数,其中pprimep\in prime
f(i)f(i)表示gcd(x,y)=igcd(x,y)=i的点对个数。

F(p)=pdf(d)F(p)=\sum_{p|d}f(d)

反演FF函数可以得到

f(p)=pdμ(dp)F(d)f(p)=\sum_{p|d}\mu(\frac{d}{p})F(d)

显然d=kp,kNd=kp,k\in N

Ans=ppdμ(dp)F(d)Ans=\sum_{p}\sum_{p|d}\mu(\frac{d}{p})F(d)

仔细考虑一下,对于每一个dd,乘以pdμ(dp)\sum_{p|d}\mu(\frac{d}{p})
所以

Ans=dF(d)pdμ(dp)Ans=\sum_d F(d)\sum_{p|d}\mu(\frac{d}{p})

F(d)=NdMdF(d)=\lfloor\frac{N}{d}\rfloor\lfloor\frac{M}{d}\rfloor可以分块处理
pdμ(dp)F(d)\sum_{p|d}\mu(\frac{d}{p})F(d)可以枚举质数pp,然后去更新它的倍数。tottot的个质数复杂度是pNNp\sum_{p}^{N}\frac{N}{p}
大概是n÷ln(n)×(ln(n))2n\div ln(n)\times (ln(n))^2 我也不太会算。
加上分块,总的复杂度是O(Nlogn+NT)O(N\log n+\sqrt{N}T)

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 1e7 + 6;
bool v[N];
int mu[N],p[N], tot;
ll s[N];
void pre(){
mu[1] = 1;
for(int i = 2; i <= 1e7; ++i) {
if(!v[i]) mu[i] = -1, p[++tot] = i;
for(int j = 1; j <= tot && i <= 1e7/p[j]; ++j){
v[i * p[j]] = 1;
if(i % p[j] == 0) {
mu[i * p[j]] = 0;
break;
}
mu[i * p[j]] = -mu[i];
}
}
for(int i = 1; i <= tot; ++i)
for(int j = 1; j <= 1e7 / p[i]; ++j)
s[j * p[i]] += mu[j];
for(int i = 1; i <= 1e7; ++i)
s[i] += s[i - 1];
}
int n, m;
ll solve() {
ll res = 0;
/* for(int i = 1; i <= tot && p[i] <= min(n, m); ++i) {
for(int j = 1; j * p[i] <= min(n, m); ++j)
res += (ll)mu[j] * (n / (p[i] * j)) * (m / (p[i] * j));
}*/
for(int i = 1, r; i <= min(n, m); i = r +1) {
r = min(n / (n / i), m / (m / i));
res += (ll)(n / i) * (m / i) * (s[r] - s[i - 1]);
}
return res;
}
int main() {
int T = read();
pre();
while(T--) {
n = read(), m = read();
writeln(solve());
}
return 0;
}