题目地址：洛谷：【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;
}