#P2522. [HAOI2011] Problem b

    ID: 1530 远端评测题 2500ms 250MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2011河南各省省选最大公约数gcd莫比乌斯反演容斥

[HAOI2011] Problem b

题目描述

对于给出的 nn 个询问,每次求有多少个数对 (x,y)(x,y),满足 axba \le x \le bcydc \le y \le d,且 gcd(x,y)=k\gcd(x,y) = kgcd(x,y)\gcd(x,y) 函数为 xxyy 的最大公约数。

输入格式

第一行一个整数 nn,接下来 nn 行每行五个整数,分别表示 a,b,c,d,ka,b,c,d,k

输出格式

nn 行,每行一个整数表示满足要求的数对 (x,y)(x,y) 的个数。

2
2 5 1 5 1
1 5 1 5 2
14
3

提示

对于 100%100\% 的数据满足:1n,k5×1041 \le n,k \le 5 \times 10^41ab5×1041 \le a \le b \le 5 \times 10^41cd5×1041 \le c \le d \le 5 \times 10^4