A2457. ZAP-Queries
编程题
提高+/省选-
知识点
题目描述
密码学家正在尝试破解一种叫 BSA 的密码。
他发现，在破解一条消息的同时，他还需要回答这样一种问题：
给出 $a,b,d$，求满足 $1 \leq x \leq a$，$1 \leq y \leq b$，且 $\gcd(x,y)=d$ 的二元组 $(x,y)$ 的数量。
因为要解决的问题实在太多了，他便过来寻求你的帮助。
他发现，在破解一条消息的同时，他还需要回答这样一种问题：
给出 $a,b,d$，求满足 $1 \leq x \leq a$，$1 \leq y \leq b$，且 $\gcd(x,y)=d$ 的二元组 $(x,y)$ 的数量。
因为要解决的问题实在太多了，他便过来寻求你的帮助。
输入格式
输入第一行一个整数 $n$，代表要回答的问题个数。
接下来 $n$ 行，每行三个整数 $a,b,d$。
接下来 $n$ 行，每行三个整数 $a,b,d$。
输出格式
对于每组询问，输出一个整数代表答案。
输入输出样例
输入 #1
2 4 5 2 6 4 3
输出 #1
3 2
说明/提示
#### 数据规模与约定
对于全部的测试点，保证 $1 \leq n \leq 5 \times 10^4$，$1 \leq d \leq a,b \leq 5 \times 10^4$。
对于全部的测试点，保证 $1 \leq n \leq 5 \times 10^4$，$1 \leq d \leq a,b \leq 5 \times 10^4$。