HKU 2023 Selection Contest D Card

题目来自 HKU 2023 Selection Contest D。原出处不明。

  This article provides a feasible solution to a certain competitive programming problem.   If you have better solutions, feel free to share with me!

Problem Description

给定两个长为 \(n\) 的数字序列 \(\{a_1, a_2, ..., a_n\}\) 与 \(\{b_1,b_2,...,b_n\}\)

你可以进行这样的操作：选择两个数 \(a_i, a_j\ (i\neq j)\) 并将其中的一个数改为 \(a_i+a_j\) 或 \(|a_i-a_j|\)。

判断在进行有限次操作后，序列 \(\{a_1,a_2,...,a_n\}\) 是否能够变为序列 \(\{b_1,b_2,...,b_n\}\)？

Tutorial

首先很容易发现该操作可以交换任意两个数；因此无须考虑顺序。

对于两数 \(a,b\)，我们能够将其中的任意一个变为 \(|a-b|\)；此时我们应该联想到一个著名的算法：

九章算术 - 更相减损术：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。

更相减损术指出，我们可以通过辗转相减的方法求出 \(a,b\) 两数的最大公约数 \(\gcd(a,b)\)。欧几里得算法 (辗转相除法) 实际上是更相减损术 (辗转相减法) 的反复应用。

例子：求 \(98\) 与 \(63\) 的最大公约数。

• \(98>63\), \(98-63=35, 63\).
• \(63>35\), \(63-35=28, 35\).
• \(35>28\), \(35-28=7,28\).
• \(28>7\), \(28-7=21, 7\).
• \(21>7\), \(21-7=14,7\).
• \(14>7\), \(14-7=7,7\).
• \(7=7\), algorithm termiates with \(\gcd(35,63)=7\).

基于更相减损术 (或欧几里得算法) 的证明，我们能够得到一个重要的性质：当 \(n=2\) 时，题目中定义的「操作」不会使 \(\gcd(a_1,a_2)\) 发生改变。推广到 \(n>2\) 的情况：无论怎样对 \(\{a_n\}\) 进行操作，\(\gcd(a_1,a_2,...,a_n)\) 都是始终不变的。

这样，我们得到：\(\gcd(a_1,a_2,...,a_n)=\gcd(b_1,b_2,...,b_n)\) 是解答该问题的一个必要条件。

如何证明其充分性，也就是，对于任意满足 \(\gcd(a_1,a_2,...,a_n)=\gcd(b_1,b_2,...,b_n)\) 的两数列 \(\{a_n\}\) 与 \(\{b_n\}\) 是否一定存在一种方法使得 \(\{a_n\}\) 最终能变为 \(\{b_n\}\)？

这样的方法是存在的：假设 \(d=\gcd(a_1,a_2,...,a_n)=\gcd(b_1,b_2,...,b_n)\)。

• 通过类似更相减损的方法对 \(\{a_n\}\) 两两求 \(\gcd\)，最终可以将整个序列变为 \(\{d\}\)。
• 同理，我们可以将 \(\{b_n\}\) 变为 \(\{d\}\)。
• 注意到更相减损的过程是可逆 (进行对应的辗转相加) 的；因此我们能从 \(\{d\}\) 还原出 \(\{b_n\}\)。
• 那么方法就很简单了：\(\{a_n\}\to\{d\}\to\{b_n\}\)。

证毕，\(\gcd(a_1,a_2,...,a_n)=\gcd(b_1,b_2,...,b_n)\) 是该问题的充分必要条件。

Code Implementation

#include <iostream>

using namespace std;

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int gcd_a, a;
        cin >> a;
        gcd_a = a;
        for (int i = 2; i <= n; ++i) {
            cin >> a;
            gcd_a = gcd(gcd_a, a);
        }
        int gcd_b, b;
        cin >> b;
        gcd_b = b;
        for (int i = 2; i <= n; ++i) {
            cin >> b;
            gcd_b = gcd(gcd_b, b);
        }
        cout << (gcd_a == gcd_b ? "Yes" : "No") << endl;
    }

    return 0;
}