P2623【HAOI2011 Day2】Problem b | |
|
问题描述
对于给出的 \(n\) 个询问,每次求有多少个数对 \((x,y)\) ,满足 \(a\le x\le b,c\le y\le 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\text{%}$ 的数据满足: $1\le n\le 50000 $, $1\le a\le b\le 50000$ , $1\le c\le d\le 50000$ , $1\le k\le 50000$