题意简述

• 给定正整数 $x,z$，求满足 $z=x\times y\times\gcd(x,y)$ 的最小正整数 $y$，若不存在，输出 $-1$。

• 每个测试点有 $t$ 次询问。

• $1\leq t\leq 5\times 10^5$，$1\leq x\leq 10^9$，$1\leq z\leq 2^{63}$

题目分析

方法一

设 $x,y,z$ 中分别含有 $x_1,y_1,z_1$ 个素因子 $2$，则 $\gcd(x,y)$ 中含有 $\min(x_1,y_1)$ 个素因子 $2$。

根据条件 $z=x\times y\times\gcd(x,y)$ 得 $z_1=x_1+y_1+\min(x_1,y_1)$，接着根据 $x_1$ 和 $y_1$ 的大小关系进行分类讨论：

• $x_1>y_1$
  此时 $z_1=x_1+2y_1$，且 $x_1>y_1\Leftrightarrow 3x_1>z_1$。注意 $z_1-x_1$ 必须为偶数，否则 $y_1$ 会出现小数的情况。

• $x_1\leq y_1$
  此时 $z_1=2x_1+y_1$，且 $x_1\leq y_1\Leftrightarrow 3x_1\leq z_1$。

综上，$y_1=\begin{cases} \dfrac{z_1-x_1}2=z_1-\dfrac{x_1}2-\dfrac{z_1}2,&3x_1>z_1\\ z_1-2x_1=z_1-\dfrac{x_1}2-\dfrac{3x_1}2,&3x_1\leq z_1 \end{cases}=z_1-\dfrac{x_1}2-\dfrac{\min(3x_1,z_1)}2$。

同理，对于其他素因子，也满足上文所述。

再将这个等式转化成 $x,y,z$ 的形式：

$$y=\dfrac z{\sqrt{x}}\div\sqrt{\gcd(x^3,z)}=\dfrac zx\div\sqrt{\gcd\left(\dfrac zx,x^2\right)} $$

方法二

令 $g=\gcd(x,y)$，得

$$z=xyg \Rightarrow\dfrac zx=yg \Rightarrow\dfrac zx=\dfrac yg\times g^2$$

根据最大公约数性质，我们有 $\gcd\left(\dfrac xg,\dfrac yg\right)=1$，可得

$$\begin{aligned} &\gcd\left(\dfrac zx,x^2\right)=\gcd\left[\dfrac yg\times g^2,\left(\dfrac xg\right)^2\times g^2\right]=g^2\\ \Rightarrow&g=\sqrt{\gcd\left(\dfrac zx,x^2\right)} \Rightarrow y=\dfrac zx\div\sqrt{\gcd\left(\dfrac zx,x^2\right)}\end{aligned}$$

根据上述两种方法，均可证明 $y=\dfrac zx\div\sqrt{\gcd\left(\dfrac zx,x^2\right)}$，故直接计算此式即可。

时间复杂度 $\Theta(t\log x^2)$。（注意计算 $\gcd$ 的时间复杂度）