【题目描述】

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<=103。 

对于40%的数据，t<=103,  x<106,  z<=109。 

对于另30% 的数据，t<104 。 

对于另20% 的数据，x<106 。 

对于100%的数据，1<=t<=5*105, 1<=x<=109, 1<=z<=263 。

【题目分析】

• 题目偏数学，一共三个变量，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*d2=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;  }

(adsbygoogle = window.adsbygoogle || []).push({});