「BZOJ2301」[HAOI2011]Problem b

Description

对于给出的nn个询问,每次求有多少个数对(x,y)(x,y),满足axba\leq x\leq bcydc\leq y\leq d,且gcd(x,y)=kgcd(x,y)=kgcd(x,y)gcd(x,y)函数为xxyy的最大公约数。

Input

第一行一个整数n,接下来n行每行五个整数,分别表示a、bbccddkk

Output

nn行,每行一个整数表示满足要求的数对(x,y)(x,y)的个数

Solution

f(i)f(i)表示x[1,n]x\in[1,n]y[1,m]y\in[1,m]gcd(x,y)=igcd(x,y)=i的数对(x,y)(x,y)数量
F(i)F(i)表示x[1,n]x\in[1,n]y[1,m]y\in[1,m]igcd(x,y)i|gcd(x,y)的数对(x,y(x,y数量

F(i)=idf(d)=nimiF(i)=\sum_{i|d}f(d)=\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor

反演FF函数得到:

f(i)=idμ(di)F(d)=idμ(di)ndmdf(i)=\sum_{i|d}\mu(\frac{d}{i})F(d)=\sum_{i|d}\mu(\frac{d}{i})\cdot \lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor

O(50000n)O(50000n)还过不了题目,分块求后面部分就能达到优秀的O(nsqrt(50000))O(nsqrt(50000))

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
#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("");}
int k;
const int N = 61000;
int miu[N];
bool v[N];
int p[N], tot;
void pre() {
miu[1] = 1;
for(int i = 2; i <= 50000; ++i) {
if(!v[i]) p[++tot] = i, miu[i] = -1;
for(int j = 1; j <= tot; ++j) {
if(p[j] > 50000/ i) break;
v[i * p[j]] = 1;
if(i % p[j] == 0) {
miu[i * p[j]] = 0;
break;
}
miu[i * p[j]] = -miu[i];
}
}
for(int i = 1; i <= 50000; ++i) miu[i] += miu[i - 1];
}
ll solve(int n, int m) {
ll res = 0;
/*for(int i = k; i <= min(n, m); i += k)
res += miu[i / k] * (n / i) * (m / i);*/
//printf("n=%d,m=%d\n",n,m);
for(int i = 1, r; i * k <= min(n, m); i = r + 1) {
r = min(n / (n / i), m / (m / i));
res += (ll)(miu[r] - miu[i - 1]) * (n / k / i) * (m / k / i);
//printf("i=%d,r=%d,%d\n", i, r,(miu[r] - miu[i - 1]) * (n / i) * (m / i));
}
return res;
}

int main() {
pre();
int T = read();
while(T--) {
int a = read(), b = read(), c = read(), d = read();
k = read();
writeln(solve(b,d) - solve(b, c - 1) - solve(a - 1, d) + solve(a - 1, c - 1));
}
return 0;
}