E. G-C-D, Unlucky! - 题解

比赛与标签

比赛: Codeforces Round 1037 (Div. 3) 标签: math, number theory 难度: *1400

喵喵，这是个什么谜题呀？

主人你好呀~！(ฅ'ω'ฅ) 这道题给了我们两个长度为 n 的数组 p 和 s，它们分别代表某个神秘数组 a 的前缀最大公约数（prefix GCD）和后缀最大公约数（suffix GCD）的说。

具体来说，如果这个神秘的数组 a 真的存在，那么：

• p[i] 就是 a[1] 到 a[i] 这些数字的最大公约数。
• s[i] 就是 a[i] 到 a[n] 这些数字的最大公约数。

我们的任务就是当一个侦探猫娘，判断一下，根据给定的 p 和 s，那个神秘的数组 a 是不是真的能被我们找出来呐？如果可以，就输出 "Yes"，不然就输出 "No" 咯~

输入格式：

• 第一行是一个整数 t，表示有 t 组测试数据。
• 每组数据包含：
  • 一个整数 n，数组的长度。
  • 一行 n 个整数，代表数组 p。
  • 一行 n 个整数，代表数组 s。

输出格式：

• 对每组数据，如果存在合法的数组 a，输出 "Yes"，否则输出 "No"。

猫娘的推理时间！思路大揭秘喵~

这道题看起来有点绕，但别怕，跟着本猫娘的思路，一步一步就能解开谜题啦！

第一步：分析 a[i] 的性质

我们来仔细看看 p[i] 和 s[i] 的定义：

• p[i] = gcd(a[1], a[2], ..., a[i])
• s[i] = gcd(a[i], a[i+1], ..., a[n])

根据最大公约数（GCD）的性质，一个数一定是它所在的一组数的 GCD 的倍数。所以呀：

1. a[i] 必须是 gcd(a[1], ..., a[i]) 的倍数，也就是说，a[i] 必须是 p[i] 的倍数。
2. a[i] 也必须是 gcd(a[i], ..., a[n]) 的倍数，也就是说，a[i] 必须是 s[i] 的倍数。

既然 a[i] 既要被 p[i] 整除，又要被 s[i] 整除，那它一定是 p[i] 和 s[i] 的公倍数，对吧？

第二步：大胆猜测，小心求证！

我们想构造一个可能的数组 a。为了让构造的 a 满足条件，我们应该给 a[i] 赋什么值呢？既然 a[i] 必须是 p[i] 和 s[i] 的公倍数，为了让限制最少（也就是让 a[i] 的值尽可能小，从而更容易满足其他数的 GCD 条件），一个最自然、最合理的选择就是取它们的最小公倍数 (LCM) 啦！

所以，我们大胆地做出一个猜测：如果存在一个合法的数组 a，那么我们构造的候选数组 a_candidate，其中 a_candidate[i] = lcm(p[i], s[i])，也一定是一个合法的解！

为什么这个猜测是正确的呢？

• 假设存在一个真正的解 a_real。我们知道 a_real[i] 必须是 lcm(p[i], s[i]) 的倍数。
• 也就是说 a_real[i] 是我们构造的 a_candidate[i] 的倍数。
• 那么 gcd(a_real[1], ..., a_real[i]) 必然是 gcd(a_candidate[1], ..., a_candidate[i]) 的倍数。
• 反过来，a_candidate[j] = lcm(p[j], s[j]) 是 p[j] 的倍数。而对于 j <= i，p[j] 又是 p[i] 的倍数（因为 p 是前缀GCD，所以是单调不增的）。所以 a_candidate[j] 一定是 p[i] 的倍数。这意味着 gcd(a_candidate[1], ..., a_candidate[i]) 也一定是 p[i] 的倍数。
• 结合这两点，可以证明，如果我们构造的候选数组都无法满足条件，那么其他任何数组也肯定不行。

所以，我们的策略就非常清晰了喵~

第三步：最终的解题流程

1. 构造候选数组：对于每一个 i，我们计算 a[i] = lcm(p[i], s[i])。这里要注意，直接用 p[i] * s[i] 可能会溢出，所以要用 (p[i] / gcd(p[i], s[i])) * s[i] 这种安全的方式来计算最小公倍数。
2. 验证候选数组：我们已经有了一个候选的数组 a，现在只需要检查它是否真的能生成给定的 p 和 s 就好啦。
   • 验证前缀 GCD：我们从左到右遍历 a，计算出它的前缀 GCD 数组，看看是否和输入的 p 数组一模一样。
   • 验证后缀 GCD：我们从右到左遍历 a，计算出它的后缀 GCD 数组，看看是否和输入的 s 数组一模一样。
3. 得出结论：如果两个验证都通过了，说明我们找到了一个合法的 a，答案就是 "Yes"！只要有任何一个验证失败，就说明不存在这样的 a，答案就是 "No" 的说。

是不是很简单清晰了呢？喵~ (´｡• ᵕ •｡`) ♡

魔法代码咏唱！

#include <iostream>
#include <vector>
#include <numeric> // C++17 引入了 std::gcd 和 std::lcm，这里用 std::gcd 就好啦~

// 一个安全计算最小公倍数(lcm)的函数喵~
// 使用 (a / gcd(a, b)) * b 可以有效防止 a * b 直接相乘导致的溢出！
long long safe_lcm(long long a, long long b) {
    if (a == 0 || b == 0) {
        return 0;
    }
    return (a / std::gcd(a, b)) * b;
}

void solve() {
    int n;
    std::cin >> n;
    std::vector<long long> p(n), s(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> p[i];
    }
    for (int i = 0; i < n; ++i) {
        std::cin >> s[i];
    }

    // 处理 n=1 的特殊情况，此时 p[0] 必须等于 s[0]
    if (n == 1) {
        if (p[0] == s[0]) {
            std::cout << "Yes\n";
        } else {
            std::cout << "No\n";
        }
        return;
    }

    // 构造我们的候选数组 a_candidate
    std::vector<long long> a_candidate(n);
    for (int i = 0; i < n; ++i) {
        // a[i] 必须是 p[i] 和 s[i] 的公倍数，我们取最小的那个！
        a_candidate[i] = safe_lcm(p[i], s[i]);
    }

    bool ok = true; // 一个 flag，用来标记我们的候选数组是否合格

    // 验证前缀 GCD 是否和 p 数组匹配
    long long current_p_gcd = 0;
    for (int i = 0; i < n; ++i) {
        if (i == 0) {
            current_p_gcd = a_candidate[i];
        } else {
            current_p_gcd = std::gcd(current_p_gcd, a_candidate[i]);
        }
        if (current_p_gcd != p[i]) {
            ok = false; // 啊哦，不匹配，直接判定失败
            break;
        }
    }

    // 如果前缀检查已经失败了，就没必要检查后缀了喵
    if (ok) {
        // 验证后缀 GCD 是否和 s 数组匹配
        long long current_s_gcd = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (i == n - 1) {
                current_s_gcd = a_candidate[i];
            } else {
                current_s_gcd = std::gcd(current_s_gcd, a_candidate[i]);
            }
            if (current_s_gcd != s[i]) {
                ok = false; // 呜呜，后缀也不匹配
                break;
            }
        }
    }

    if (ok) {
        std::cout << "Yes\n";
    } else {
        std::cout << "No\n";
    }
}

int main() {
    // 加速输入输出，让程序跑得飞快~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

时空魔法的消耗分析~

• 时间复杂度: O(N * log(V)) 的说。

  • 对于每个测试用例，我们需要遍历数组来构造 a_candidate，这需要 N 次 lcm 计算。lcm 的计算依赖于 gcd，gcd 的复杂度大约是 O(log(V))，其中 V 是数组中元素的最大值。
  • 接着，我们还需要两次遍历来验证前缀和后缀 GCD，每次遍历都包含 N 次 gcd 计算。
  • 所以总的时间复杂度就是 O(N * log(V)) 啦。

• 空间复杂度: O(N) 的说。

  • 我们需要存储输入的 p 和 s 数组，以及我们构造的 a_candidate 数组，它们的大小都是 N。所以空间消耗是线性的。

猫娘的小课堂时间~

这次的解题之旅是不是很有趣呀？我们来总结一下学到了什么吧！

1. GCD 与 LCM 的深刻联系：这道题的核心就是利用 a[i] 必须是 p[i] 和 s[i] 的公倍数这一性质。这提醒我们，在处理与 GCD 相关的数论问题时，要时刻想着它的好朋友 LCM 喵~
2. 构造与验证思想：当直接求解困难时，可以尝试根据问题的约束条件，构造一个最有可能满足条件的“候选解”，然后去验证它是否正确。如果能证明这个候选解的可行性等价于原问题有解，那么问题就迎刃而解了！
3. 注意编程细节：
   • 安全计算 LCM：lcm(a, b) = (a / gcd(a, b)) * b 是一个防止整数溢出的好习惯，要记住哦！
   • 利用标准库：C++17 的 <numeric> 头文件提供了 std::gcd，非常方便，就不用自己手写啦。

希望这篇题解能帮到你！继续努力，享受解题的乐趣吧，喵~ ٩( 'ω' )و