1460 - 最大公约数

通过次数

提交次数

新版界面

时间限制 : 1 秒

内存限制 : 128 MB

$T$ 组数据，每一组数据给定 $l,r,x$ ，试求： $\gcd(\lfloor \frac{l}{x}\rfloor,\lfloor \frac{l+1}{x}\rfloor,\cdots,\lfloor \frac{r}{x}\rfloor)$ 的值。

其中 $\gcd$ 表示求最大公约数，例如 $\gcd(6,9)=3$ ， $\gcd(2,4,8)=2$ ， $\gcd(5,6,7)=1$ 。特别地，我们定义一个正整数的最大公约数是它自身。
$\lfloor x \rfloor$ 表示 $x$ 向下取整，例如 $\lfloor 3.14 \rfloor=3$ 。

提示

【样例解释和说明】

样例中的 $T=4$ ，说明有 $4$ 组数据。

对于第一组数据， $l=3,r=6,x=1$ ，即求 $\gcd(\lfloor \frac{3}{1}\rfloor,\lfloor \frac{4}{1} \rfloor, \lfloor \frac{5}{1}\rfloor,\lfloor \frac{6}{1}\rfloor)=1$ 。
对于第二组数据， $l=8,r=11,x=4$ ，即求 $\gcd(\lfloor \frac{8}{4} \rfloor,\lfloor \frac{9}{4} \rfloor,\lfloor \frac{10}{4}\rfloor,\lfloor \frac{11}{4}\rfloor)=\gcd(2,2,2,2)=2$ 。
对于第三组数据， $l=4,r=4,x=3$ ，即求 $\gcd(\lfloor \frac{4}{3}\rfloor)=1$ 。
对于第四组数据，类似可得结果是 $1$ 。

第一行输入一个正整数 $T$ ，表示数据组数。

对于每一组数据，输入一行三个正整数 $l,r,x$ ，以空格隔开。

对于每一组数据，输出一行，一个正整数表示答案。