【题解】数学游戏
【题目描述】
Kri 喜欢玩数字游戏。 一天,他在草稿纸上写下了t 对正整数(x,y) ,并对于每一对正整数计算出了z=x*y*gcd(x,y);可是调皮的 Zay 找到了 Kri 的草稿纸,并把每一组的 y都擦除了,还可能改动了一些 z。
现在 Kri 想请你帮忙还原每一组的 y,具体地,对于每一组中的 x和 z,你需要输出最小的正整数 y,使得 z=x*y*gcd(x,y) 。如果这样的 y不存在,也就是 Zay 一定改动了z ,那么请输出 -1。 注:gcd(x,y) 表示 x和 y的最大公约数,也就是最大的正整数 d,满足 既是x 的约数,又是 y的约数。
【输入描述】
第一行一个整数 t ,表示有 对正整数 x和z 。
接下来 t 行,每行两个正整数 x和z ,含义见题目描述。
【输出描述】
对于每对数字输出一行,如果不存在满足条件的正整数y ,请输出-1 ,否则输出满足条件的最小正整 数 y。
【样例输入1】
1 10 240
【样例输出1】
12
【样例1解释】
x*y*gcd(x,y)=10*12*gcd(10,12)=240
【样例输入2】
3 5 30 4 8 11 11
【样例输出2】
6 -1 1
【数据范围】
对于20%的数据,t,x,z<=103。
对于40%的数据,t<=103, x<106, z<=109。
对于另30% 的数据,t<104 。
对于另20% 的数据,x<106 。
对于100%的数据,1<=t<=5*105, 1<=x<=109, 1<=z<=263 。