【题解】数学游戏
【题目描述】
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;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。