【题目描述】

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<=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⁶³ 。

【题目分析】

• 题目偏数学，一共三个变量，x,y,z。如果z改变过就输出 -1。

• 需要进行简单的等式变换。用换元法，因为每组的y都被擦除了，所以gcd(x,y)无法直接计算。那么我们假设gcd(x,y)=d。

  我们用这个关系来反向表示一下x和y。因为d是x和y的公约数，所以一定存在两个变量使得

  p*d=x,      （比如样例中5*2=10）

  q*d=y。   （比如样例中6*2=12）

  那么原式可以变成 （p*d）  *  （q * d） * d = z。 因为 z和x 已知，所以就变成  q*d²=z/x 。

• 算到上一步的时候，我们考虑用暴力穷举法（只提供思路，因为数据量太大不能得满分）。可以看出，未知量就是q和d。我们只要双重循环不断枚举，成立的值便输出，如果一个没成立则输出-1。

• 如果上一步成立，那么q*d就是我们要的结果。

• 注意，我们还应该验证一个问题，就是求出y后，gcd(x,y)的值是不是d。如果不是，那么也不是我们要求的结果。

【参考答案1】——模拟法因为数据量过大不能得满分

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
	return __gcd(a,b);  //求最大公约数的函数，考试禁用 
}
int x,z;
int main() {
//	freopen("math.in","r",stdin);
//	freopen("math.out","w",stdout);
	int m;
	cin>>m;
	while(m--){
		cin>>x>>z;
		int n=z/x;
		int flag=0;  //标志位，为1说明这一轮当中找到了答案 
		for(int q=1; q<=n; q++) {
			for(int d=1; d<=n; d++) {
				if(q*d*d==n && gcd(x,q*d)==d) {
					//如果符合此公式，而且 最大公约数存在，那么q*d就是y 
					cout<<q*d<<endl;
					flag=1;
					break;
				}
			}
		}
		//flag为0表示不存在 
		if(!flag){
			cout<<"-1"<<endl;
		}
	}
	return 0;
}