3657. [NOI Online 2022 1st PJ]数学游戏

【题目描述】

Kri 喜欢玩数字游戏。

一天，他在草稿纸上写下了$t$对正整数$(x,y)$，并对于每一对正整数计算出了$z=x\times y\times \gcd(x,y)$。

可是调皮的 Zay 找到了 Kri 的草稿纸，并把每一组的$y$都擦除了，还可能改动了一些$z$。

现在 Kri 想请你帮忙还原每一组的$y$，具体地，对于每一组中的$x$和$z$，你需要输出最小的正整数$y$，使得$z=x\times y\times \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】

1
10 240

【样例输出1】

12

【样例1说明】

$x\times y\times \gcd(x,y)=10\times 12\times\gcd(10, 12)=240$

【样例输入2】

3
5 30
4 8
11 11

【样例输出2】

6
-1
1

测试样例下载

【数据规模与约定】

对于20%的数据，$t,x,z\leq 10^3$。

对于40%的数据，$t\leq 10^3,x\leq 10^6,z\leq 10^9$。

对于另30%的数据，$t\leq 10^4$。

对于另20%的数据，$x\leq 10^6$。

对于100%的数据， $1\leq t\leq 5\times 10^5,1\leq x\leq 10^9,1\leq z<2^{63}$。

【来源】

NOI Online 2020 1st 普及组 T2