如何确定数组中的所有对是否具有相同的最优 GCD？

Question

我正在尝试以下竞争性编程问题：

G。 GCDland 神秘阵
每次测试时间限制1秒
每个测试的内存限制 256 MB

在GCDland这个古怪的小镇里，住着一位名叫西奥的数学家，他有着狂野偏执的阴谋论。西奥坚信，在某些神秘的数组中，每对可能的数字的最大公约数 (GCD) 总是相同的。他认为这些阵列是来自古代文明的信息，试图通过数字与我们沟通。

西奥的朋友们认为他已经走入了深渊，但他决心证明他们是错的，并揭开这些阵列背后的真相。他需要你的帮助来验证他的理论。给定一个整数数组，您的任务是确定数组中每对数字的 GCD 是否确实相同。如果 Theo 的理论对于给定的数组成立，你应该确认它；否则，你应该揭穿它。

两个数的 GCD 是两个数相除不留余数的最大正整数。

输入
第一行包含一个整数 𝑁 (2≤𝑁≤100,000)，即数组中元素的数量。
第二行包含𝑁整数𝐴𝑖(1≤𝐴𝑖≤10^7)，即数组的元素。

输出
如果数组中每对数字的 GCD 相同，则打印“YES”。否则，打印“NO”。

您可以在这里查看codeforces问题。

这是我的代码：

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


int solve()
{
    int n;
    cin >> n;
    vector<int> v;


    int first, second;
    cin >> first >> second;
    v.push_back(first);
    v.push_back(second);

    const int x = gcd(v[0], v[1]);

    for (int i = 2; i < n; i ++)
    {
        int newval;
        cin >> newval;
        v.push_back(newval);
        for (int j = 0; j < i; j++)
        {
            //cout << "Starting gcd(" <<v[i]<< "," <<v[j]<<")"<< endl;
            if (x != gcd(v[i], v[j]))
            {
                cout << "NO\n";
                return 0;
            }
        }
    }
    cout << "YES\n";
    return 0;
}

由于时间限制失败了，所以我尝试将具有记忆功能的

gcd()

函数优化为以下函数：

int gcd(int a, int b,  map<pair<int,int>, int> &hashmap) {

    if (b == 0)
    {
        return a;
    }

    pair<int,int> key = make_pair(a,b);
    auto it = hashmap.find(key);

    if (it != hashmap.end())
    {
        return it->second;
    }
    else
    {
        int result = gcd(b, a % b, hashmap);
        hashmap.emplace(key, result);
        return result;
    }
}

它在某些测试用例上速度更快，但总体上仍然失败。我无法联系教练，真的不知道该怎么办。我还认为一定有更好的方法来比较每一对，但没有成功。

Answer 1

一种常见的优化策略是避免做不需要的事情。在你的例子中，你确定每对的 GCD，只是为了找出它们是否都具有相同的 GCD。然而，它只需要一对具有不同 GCD 即可获得结果。

看待这个问题的不同方法是将数字视为其素因数的乘积。例如。 105=3×5×7，28=2×2×7。这些质因数可以出现多次，并且每个数字只有一组质因数。 GCD 也是由质因数组成的。 105 和 28 的 GCD 是 7，这只是集合 {3,5,7} 和 {2,2,7} 的重叠。

关于实现，如果您仅限于小（如 32 位）数字，则它们可以表示的素数集是有限的，因此拥有这些素数的硬编码列表是可能的，并且可能是值得的。您可以检查这些素数并验证每个输入是否都将其作为素因数。如果所有数字都有该质因数，那么它就是 GCD 的一部分。如果质因数恰好以零或一个数字出现，那也很好。请注意，质因数可以在同一数字中出现多次。而且，它可以出现在数字的 GCD 和非 GCD 因子中。

备注：

• 对于该实现的大部分部分，您可以忽略质因数出现的频率，因此您可以使用单个位来表示它是否存在。这允许使用高效的按位运算。
• 您可以从前两个数字确定可疑的 GCD。然后可以先将所有其他数字除以该数字，看看它是否是公因数。然后可以扫描结果中的质因数。这可以轻松减少您甚至需要检查的素数范围。