自动搬运

查看原文

来自洛谷，原作者为

	enucai Remake.

搬运于2025-08-24 22:37:23，当前版本为作者最后更新于2022-03-26 18:35:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Preface

考场上没想出来，好一道人类智慧题！

Analysis1

较简单的证明。

若 $x\nmid z$，则一定无解。

令 $x=d\times a$，$y=d\times b$，其中 $\gcd(a,b)=1$。那么有 $\gcd(x,y)=d$。则 $z=x\times y\times \gcd(x,y)=d^3\times a\times b$。

我们知道 $x$ 与 $z$，那么可以求出 $\frac{z}{x}=d^2\times b$。由于 $\gcd(a,b)=1$，所以 $\gcd(\frac{z}{x},x^2)=\gcd(d^2\times b,d^2\times a^2)=d^2$。若 $\gcd(\frac{z}{x},x^2)$ 不是完全平方数，则无解。

将 $\gcd(\frac{z}{x},x^2)$ 开方即可得到 $d$。那么：

$$\frac{\frac{z}{x}}{\sqrt{\gcd(\frac{z}{x},x^2)}}=\frac{d^2\times b}{d}=d\times b=y $$

所以我们有：

$$y=\frac{\frac{z}{x}}{\sqrt{\gcd(\frac{z}{x},x^2)}} $$

时间复杂度 $O(T\log x)$。

Analysis2

更繁琐的证明。

由于 $z=x\times y\times \gcd(x,y)$，两边同除 $x$，得：$\frac{z}{x}=y\times \gcd(x,y)$。若 $x\nmid z$，则一定无解。

根据唯一分解定理，我们对已知的 $x$、$\frac{z}{x}$ 与要求的 $y$ 分解质因数：

$$\begin{cases} \frac{z}{x}=p_1^{a_1}\times p_2^{a_2}\times p_3^{a_3}\times \dots \times p_k^{a_k}\\ x=p_1^{b_1}\times p_2^{b_2}\times p_3^{b_3}\times \dots \times p_k^{b_k}\\ y=p_1^{c_1}\times p_2^{c_2}\times p_3^{c_3}\times \dots \times p_k^{c_k} \end{cases} $$

由于 $\frac{z}{x}=y\times \gcd(x,y)$，所以对于任意 $i\in[1,k]$，有 $a_i=c_i+\min(b_i,c_i)$。

接下来分两种情况讨论：

• 当 $b_i\le c_i$ 时，$a_i=b_i+c_i$，则 $c_i=a_i-b_i$。

  该种情况满足：$b_i\le c_i\iff b_i\le a_i-b_i\iff b_i\le \frac{a_i}{2}$

• 当 $b_i>c_i$ 时，$a_i=2\times c_i$，则 $c_i=\frac{a_i}2$。

  该种情况满足：$b_i>c_i\iff b_i>\frac{a_i}{2}$。

合并一下，得到 $c_i=a_i-\min(\frac{a_i}{2},b_i)$。

两边同时乘以 $2$ 得：$2\times c_i=2\times a_i-\min(a_i,2\times b_i)$。

最后转化为人话，即：

$$y^2=\frac{(\frac{z}{x})^2}{\gcd(\frac{z}{x},x^2)}$$

两边同时开方，得：

$$y=\frac{\frac{z}{x}}{\sqrt{\gcd(\frac{z}{x},x^2)}} $$

如果 $\gcd(\frac{z}{x},x^2)$ 不是完全平方数，也是无解。

时间复杂度：$O(T\log x)$。

Code

Talk is cheap, show me the code.

// And in that light, I find deliverance.
#define int long long
void work(){
	int x,z;read(x,z);
	if(z%x!=0){puts("-1");return;}
	int tmp=__gcd(z/x,x*x);
	int sq=(int)sqrt(tmp);
	if(sq*sq!=tmp) puts("-1");
	else cout<<(z/x)/sq<<endl;
}
signed main(){
	int T;read(T);
	while(T--) work();
}