#P2522. [HAOI2011] Problem b
[HAOI2011] Problem b
题目描述
对于给出的 个询问,每次求有多少个数对 ,满足 ,,且 , 函数为 和 的最大公约数。
输入格式
第一行一个整数 ,接下来 行每行五个整数,分别表示 。
输出格式
共 行,每行一个整数表示满足要求的数对 的个数。
2
2 5 1 5 1
1 5 1 5 2
14
3
提示
对于 的数据满足:,,。
对于给出的 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) 的个数。
2
2 5 1 5 1
1 5 1 5 2
14
3
对于 100% 的数据满足:1≤n,k≤5×104,1≤a≤b≤5×104,1≤c≤d≤5×104。