【小码匠自习室】 [NOI Online 2022 入门组] 数学游戏：我爆零了

小码匠

发布于 2022-06-16 18:17:48

36100

代码可运行

文章被收录于专栏：小码匠和老码农小码匠和老码农

运行总次数：0

代码可运行

碎碎念

这是一道让人伤心的题，当时参加线上赛，先通读了三道题，感觉以当时的水平，第三题搞不定，第一道、第二道可以;
正好当时正在读这本数论的书，不就是辗转相除法吗...

代码编写完毕后，验证了测试用例，测试用例都通过了。
- 其实是样例中部分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

1
10 240

输出 #1

输入 #2

输出 #2

6
-1
1

输入 #3

见附件中的 math3.in

输出 #3

见附件中的 math3.out

输入 #4

见附件中的 math4.in

输出 #4

见附件中的 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;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-06-13，如有侵权请联系 cloudcommunity@tencent.com 删除

海外加速

游戏

本文分享自小码匠和老码农微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

海外加速

游戏

登录后参与评论

0 条评论

热度