「NOI Online 2022 入门组」数学游戏 - 数论

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

Kri 喜欢玩数字游戏。

一天，他在草稿纸上写下了 \(t\) 对正整数 \((x, y)\)，并对于每一对正整数计算出了 \(z = xy \gcd(x, y)\)。

可是调皮的 Zay 找到了 Kri 的草稿纸，并把每一组的 \(y\) 都擦除了，还可能改动了一些 \(z\)。

现在 Kri 想请你帮忙还原每一组的 \(y\)，具体地，对于每一组中的 \(x\) 和 \(z\)，你需要输出最小的正整数 \(z\)，使得 \(z = xy \gcd(x, y)\)。如果这样的 \(y\) 不存在，也就是 Zay 一定改动了 \(z\)，那么请输出 \(-1\)。

数据范围：\(1 \le t \le 5 \times {10}^5\)，\(1 \le x \le {10}^9\)，\(1 \le z < 2^{63}\)。

解题思路

很明显这是一道数论题。

我们可以设 \(x = m \gcd(x, y)\)，\(y = n \gcd(x, y)\)，显然 \(\gcd(m, n) = 1\)。对于 \(z = xy \gcd(x, y)\)，我们可以变形为 \(\frac{z}{x} = y \gcd(x, y)\)。又显然 \(\gcd(x, y) = \frac{x}{m}\)，\(y = \frac{nx}{m}\)，故该式可变形为 \(\frac{z}{x} = \frac{nx^2}{m^2}\)，即 \(\frac{z}{x^3} = \frac{n}{m^2}\)。又由于 \(\gcd(m, n) = 1\)，故两者无相同非 \(1\) 因子，故 \(\gcd(m^2, n) = 1\)。故我们可以求出 \(\gcd(z, x^3)\)，从而求出 \(m = \sqrt{\frac{x^3}{\gcd(z, x^3)}}\) 和 \(n = \frac{z}{\gcd(z, x^3)}\)，进而得出答案。

对于无解，由于 \(z = xy \gcd(x, y)\)，且 \(y\), \(\gcd(x, y)\), \(m\) 均为整数，故我们仅需判断 \(m = \sqrt{\frac{x^3}{\gcd(z, x^3)}}\) 和 \(\frac{z}{x}\) 是否为整数即可。

注意一下这里 \(x^3\) 可能会超出 long long 的范围，这时我们用 __int128_t 代替一下即可。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <cmath>
#include <iostream>

typedef long long ll;

ll gcd(__int128_t a, __int128_t b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    int t;

    std::cin >> t;

    while (t--) {
        ll x, z;

        scanf("%lld%lld", &x, &z);

        if (z % x != 0) {
            printf("-1\n");
            continue;
        }

        ll g = gcd(z, (__int128_t)x * x * x);
        ll n = z / g;
        ll m = sqrt((__int128_t)x * x * x / g);

        if (sqrt((__int128_t)x * x * x / g) != m) printf("-1\n");
        else printf("%lld\n", n * x / m);
    }

    return 0;
}