碎碎念
- 这是一道让人伤心的题，当时参加线上赛，先通读了三道题，感觉以当时的水平，第三题搞不定，第一道、第二道可以;
- 正好当时正在读这本数论的书，不就是辗转相除法吗...
- 代码编写完毕后，验证了测试用例，测试用例都通过了。
- 其实是样例中部分case没有通过，但数据太多，没有一个一个比对，只是看了头尾和中间的数据，发现结果都是对，以为就万事大吉...
- 洛谷给这道题难度：提高 /省选
- 肯定是达不到的，省选题这种难度，对高水平选手就不友好了，不过对于我来说，肯定是开心的乐起来
标签
- 数学、最大公约数
题目地址
- [NOI Online 2022 入门组] 数学游戏
- https://www.luogu.com.cn/problem/P8255
题目描述
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，满足 d 既是 x 的约数，又是 y 的约数。
输入格式
第一行一个整数 ，表示有 t 对正整数 x 和 z。
接下来 t 行，每行两个正整数 x 和 z，含义见题目描述。
输出格式
对于每对数字输出一行，如果不存在满足条件的正整数 y，请输出 -1，否则输出满足条件的最小正整数 y。
输入输出样例
输入 #1
代码语言：javascript复制1
10 240
输出 #1
代码语言：javascript复制12
输入 #2
代码语言：javascript复制3
5 30
4 8
11 11
输出 #2
代码语言：javascript复制6
-1
1
输入 #3
代码语言：javascript复制见附件中的 math3.in
输出 #3
代码语言：javascript复制见附件中的 math3.out
输入 #4
代码语言：javascript复制见附件中的 math4.in
输出 #4
代码语言：javascript复制见附件中的 math4.out
说明/提示
【样例 1 解释】
x×y×gcd(x,y)=10×12×gcd(10,12)=240。
【数据范围】
题解
小码匠题解
- 这是比赛成绩出来后，又重写的代码，代码不够简洁
#include <iostream>
#include <cmath>
#define endl 'n';
using namespace std;
int main() {
cout.setf(ios::fixed, ios::floatfield);
cout.precision(0);
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
long long x, z;
long long y_d;
long long a, b, e, d;
for (int i = 0; i < t; i ) {
cin >> x >> z;
if (z % x != 0) {
cout << -1 << endl;
continue;
}
y_d = z / x;
a = x * x;
b = y_d;
while (a % b != 0) {
e = b;
b = a % b;
a = e;
}
long n = sqrt(b);
if (n == sqrt(b)) {
d = y_d / sqrt(b);
if (d == y_d / sqrt(b)) {
cout << y_d / sqrt(b) << endl;
} else {
cout << -1 << endl;
}
} else {
cout << -1 << endl;
}
}
return 0;
}
