题解 P9473 [yLOI2022] 西施江南

以此记录初入洛谷的自己写的题解，虽然没通过。

算法概述

本题需使用 map 和数论知识。

题意讲解

设 是这些数的最大公约数， 是这些数的最小公倍数；求一组数据中的 是否等于 。

暴力做法（44分）

这题大家最容易想到的方法就是将 以及 都算出来再去比对，可是数据范围限制了 肯定会炸long long，所以我们直接 Pass 掉这种做法。

数论——质因数分解（76分）

如果 ，那么 和 肯定有相同的质因子且质因子的指数相同。

根据上面这个理论，我们可以通过分解 和 的质因子来进行比对。

贴代码：

#include <bits/stdc++.h>
using namespace std;
int t, n, a[500005];
int gcd(int a, int b)
{
    if (!b)
        return a;
    return gcd(b, a % b);
}
void solve()
{
    unordered_map<int, int> l_g, a1_an;
    int g = 0;
    cin >> n;

    // 分解质因子（a1至an, lcm) + 求gcd。
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        g = gcd(g, a[i]);
        int x = a[i];
        int cnt = 0;
        for (int j = 2; j * j <= x; j++)
        {
            cnt = 0;
            if (x % j == 0)
            {
                while (x % j == 0)
                {
                    cnt++;
                    x /= j;
                }
                a1_an[j] += cnt;
                l_g[j] = max(l_g[j], cnt); // 几个数的lcm等于他们共同的质因子求最高次幂。
            }
        }
        if (x != 1)
        {
            a1_an[x] += 1;
            l_g[x] = max(l_g[x], 1);
        }
    }

    // 直接将gcd的质因子累加到gcd里即可。
    for (int i = 2; i * i <= g; i++)
    {
        int cnt = 0;
        if (g % i == 0)
        {
            while (g % i == 0)
            {
                cnt++;
                g /= i;
            }
            l_g[i] += cnt;
        }
    }
    if (g != 1)
        l_g[g] += 1;

    if (l_g == a1_an) // 最后比较其质因子是否相等。
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}
int main()
{
    cin >> t;
    while (t--)
        solve();
    return 0;
}

数论——判断是否互素（AC）：

我们通过测试样例可以看出满足条件的数据中的任意两个数都是互素的关系。

为什么呢？我们来证明一下：

设 分别为两个数据。

如果 两个数互素，那么 肯定为 1， 肯定为 ，，所以很显然：如果两个数互素，那么他们的最大公约数乘最小公倍数一定等于两个数相乘。

怎么判断？用分解质因数的方式，如果有相同的质因子就输出No，反之则输出Yes。

贴代码：

// 使用map实现。
#include <bits/stdc++.h>
using namespace std;
int t, n, a[500005];
int gcd(int a, int b)
{
    if (!b)
        return a;
    return gcd(b, a % b);
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    if (n == 2)
    {
        cout << "Yes" << endl;
        return;
    }
    unordered_map<int, int> have;
    for (int i = 1; i <= n; i++)
    {
        int x = a[i];
        for (int j = 2; j * j <= x; j++)
        {
            if (x % j == 0)
            {
                if (have.count(j)) // 使用count函数来判断是否有相同的质因子。
                {
                    cout << "No" << endl;
                    return;
                }
                have[j] = 1; // 如果没有则加入进去。
                while (x % j == 0)
                    x /= j;
            }
        }
        if (x != 1)
        {
            if (have.count(x))
            {
                cout << "No" << endl;
                return;
            }
            have[x] = 1;
        }
    }
    cout << "Yes" << endl;
}
int main()
{
    cin >> t;
    while (t--)
        solve();
    return 0;
}

点我返回题目