2022NOI online（普及组）T2数字游戏

· · 个人记录

NOI online 普及T1 比较简单，直接T2；

这题十分偏数学，需要推式子；当时考试时候脑子太混乱，没有想到推式子，只能暴力。

开始的朴素想法：

令

p = z \div x

从 1 枚举到 gcd(p, x) ，枚举的是 d = gcd(x, y)； 之后再使 y = p \div i 再看一看 P = x \times y \times gcd(x, y) 是否等于 x 。这样可以得到 40pts .

接下来是代码：

//T2
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

typedef unsigned long long ULL;

ULL gcd(ULL a, ULL b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    freopen("math.in", "r", stdin);
    freopen("math.out", "w", stdout);
    int T;
    cin >> T;
    while (T -- )
    {
        bool flag = false;
        ULL x, z;
        scanf("%llu%llu", &x, &z);
        ULL p = z / x;
        if (z == x) puts("1");
        else 
        {
            ULL ans = z;
            ULL mod = gcd(p, x);
            for (ULL i = 1; i <= mod; i ++ )
            {
                ULL sum = p / i;
                if (sum * gcd(sum, x) * x == z) ans = min(ans, sum), flag = true; 
            }
            if (flag) cout << ans << endl;
            else cout << -1 << endl;
        }
    }   
    return 0;
}

奥，对了，开 long long 也可以。

考完之后，看了个式子推得很漂亮，所以就借鉴了一下：

首先

令

d = gcd(x, y) x = a \times d y = b \times d

则

z = a \times b \times d^3 (a, b) = 1 (a^2, b) = 1 (a^2\times d^2, b \times d^2) = d^2 (x^2, \dfrac{z}{x}) = d^2 d = \sqrt{(x^2, \dfrac{z}{x})}

最后就推出来了

y = \dfrac{z}{x \times \sqrt{(x ^ 2, \dfrac{z}{x})}}

写代码时一定记得要判断有没有解。 下面是 100pts 的 code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;

LL gcd(LL a, LL b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    freopen("math.in", "r", stdin);//文件输入；
    freopen("math.out", "w", stdout);//文件输出；
    int T;
    cin >> T;
    while (T -- )
    {
        LL x, y, z;
        scanf("%lld%lld", &x, &z);
        LL p = z / x;
        // int maxn = gcd(x * x, p);
        LL mod = sqrt(gcd(x * x, p));
        y = p / mod;
        if (p % mod == 0 && x * y * gcd(x, y) == z) printf("%lld\n", y);
        else puts("-1");
    }
    return 0;
}

好了，今天就这样，掰掰。