[HAOI2011]Problem b 题解
题目地址:洛谷:【P2522】[HAOI2011]Problem b – 洛谷、BZOJ:Problem 2301. — [HAOI2011]Problem b
题目描述
对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数。
输入输出格式
输入格式:
第一行一个整数n,接下来n行每行五个整数,分别表示a、b、c、d、k
输出格式:
共n行,每行一个整数表示满足要求的数对(x,y)的个数
输入输出样例
输入样例#1:
2 2 5 1 5 1 1 5 1 5 2
输出样例#1:
14 3
说明
100%的数据满足:1≤n≤50000,1≤a≤b≤50000,1≤c≤d≤50000,1≤k≤50000
题解
这个题[POI2007]ZAP-QUERIES的一个强化版。我们考虑使用容斥原理,答案即ans([1, b], [1, d])-ans([1, a-1], [1, d])-ans([1, b], [1, c-1])+ans([1, a-1], [1, c-1])。
总复杂度O(n \sqrt{n})。
代码
// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(!isdigit(c)) {
if(c == '-') neg = -1;
c = fgc();
}
while(isdigit(c)) {
res = (res << 1) + (res << 3) + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 50005;
bool notprime[MAXN];
int prime[MAXN], miu[MAXN], ptot;
inline void sieve() {
miu[1] = 1;
for(int i = 2; i < MAXN; i++) {
if(!notprime[i]) {
prime[ptot++] = i;
miu[i] = -1;
}
for(int j = 0; j < ptot && prime[j] * i < MAXN; j++) {
int k = prime[j] * i;
notprime[k] = true;
if(i % prime[j] == 0) {
miu[k] = 0; break;
} else {
miu[k] = -miu[i];
}
}
}
for(int i = 2; i < MAXN; i++) {
miu[i] += miu[i - 1];
}
}
inline LL cal(int b, int d, int k) {
LL all = 0;
if(!k) return 0;
b /= k; d /= k;
if(b > d) std::swap(b, d);
for(int i = 1; i <= b;) {
int j = std::min(b / (b / i), d / (d / i));
all += 1ll * (miu[j] - miu[i - 1]) * (b / i) * (d / i);
i = j + 1;
}
return all;
}
int T, a, b, c, d, k;
int main() {
sieve();
T = readint();
while(T--) {
a = readint(); b = readint(); c = readint(); d = readint(); k = readint();
printf("%lld\n", cal(b, d, k) - cal(a - 1, d, k) - cal(b, c - 1, k)
+ cal(a - 1, c - 1, k));
}
return 0;
}