P5399: 数学游戏(math)

---

【题目描述】

题⽬描述
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，满⾜ d既是 x 的约数，⼜是 y 的 约数。

【输入】

输⼊格式

第⼀⾏⼀个整数 t，表⽰有 t 对正整数x 和 z。

接下来 t ⾏，每⾏两个正整数 x 和 z，含义⻅题⽬描述。

【输出】

输出格式

对于每对数字输出⼀⾏，如果不存在满⾜条件的正整数 y，请输出

-1，否则输出满⾜条件的最小正整数 y。

【提示】

样例 1 解释

 X*y*gcd(x,y)=10*12*gcd(10,12)=240

样例 2 输⼊

3

5 30

4 8

11 11

样例 2 输出

6

-1

1

附加样例

⻅样例⽬录下的 math3.in 和 math3.out ，以及 math4.in 和 math4.out 。

数据范围

对于 20% 的数据， t,x,z≤10³。

对于 40% 的数据， t≤10³,x≤10⁶,z≤10⁶。

对于另 30% 的数据， t≤10⁴。

对于另 20 % 的数据， x≤10⁶。

对于 100% 的数据，1≤t≤5*10⁵,1≤x≤10⁹,1≤z≤2⁶³。

题目类型~

NOIOnline2022普及组 

咻咻~

提交答案 状态 返回