如何最优判断数组所有数对的GCD是否相同？代码超时求优化

问题背景 #

• 题目要求：判断给定数组中每一对整数的最大公约数（GCD）是否完全相同，满足条件输出YES，否则输出NO。
• 输入参数：数组长度N（2≤N≤100000），N个范围在1到10^7的整数。
• 限制条件：时间限制1秒，内存限制256MB。

当前问题 #

初始代码因时间复杂度过高超时，尝试用记忆化优化GCD函数后仍未解决超时问题。

初始GCD函数及主逻辑 #

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;
    }
}

需求 #

寻求最优解法指导，解决超时问题。

内容的提问来源于stack exchange，提问作者Tomás Molina Pérez Diez