题目地址：洛谷：【P3455】[POI2007]ZAP-Queries – 洛谷、BZOJ：Problem 1101. — [POI2007]Zap

题目描述

FGD正在破解一段密码，他需要回答很多类似的问题：对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a，y<=b，并且gcd(x,y)=d。作为FGD的同学，FGD希望得到你的帮助。

输入输出格式

输入格式：
第一行包含一个正整数n，表示一共有n组询问。（1<=n<= 50000）接下来n行，每行表示一个询问，每行三个
正整数，分别为a,b,d。（1<=d<=a,b<=50000）

输出格式：
对于每组询问，输出到输出文件zap.out一个正整数，表示满足条件的整数对数。

输入输出样例

输入样例#1：

2
4 5 2
6 4 3

输出样例#1：

3
2

说明

对于第一组询问，满足条件的整数对有(2,2)，（2,4），（4，2）。对于第二组询问，满足条件的整数对有（
6,3），（3,3）。

题解

这个题[HDU1695]GCD的一个强化版，把方法搬上来套一个整除分块就好。
总复杂度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];
    }
}

int T, b, d, k;

int main() {
    sieve();
    T = readint();
    while(T--) {
        LL all = 0, rep = 0;
        b = readint(); d = readint(); k = readint();
        if(!k) {
            printf("0\n");
            continue;
        }
        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;
        }
        printf("%lld\n", all);
    }
    return 0;
}