How to determine if all pairs in an array have the same GCD optimally?

I am trying the following competitive programming problem:

G. GCDland Mystical Arrays
time limit per test 1 second
memory limit per test 256 megabytes

In the eccentric town of GCDland, there lives a mathematician named Theo, who has a wild and paranoid conspiracy theory. Theo is convinced that in certain mystical arrays, the greatest common divisor (GCD) of every possible pair of numbers is always the same. He believes that these arrays are messages from an ancient civilization trying to communicate with us through numbers.

Theo's friends think he's gone off the deep end, but he's determined to prove them wrong and uncover the truth behind these arrays. He needs your help to validate his theory. Given an array of integers, your task is to determine whether the GCD of every pair of numbers in the array is indeed the same. If Theo's theory holds true for the given array, you should confirm it; otherwise, you should debunk it.

The GCD of two numbers is the largest positive integer that divides both numbers without leaving a remainder.

Input
The first line contains an integer 𝑁 (2≤𝑁≤100,000), the number of elements in the array.
The second line contains 𝑁integers 𝐴𝑖(1≤𝐴𝑖≤10^7), the elements of the array.

Output
Print "YES" if the GCD of every pair of numbers in the array is the same. Otherwise, print "NO".

You can look at the codeforces problem here.

This is my code:

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

It fails because of time limit, so I tried optimizing the gcd() function with memoization to the following function:

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

And it made it faster on certain test cases, but it still fails overall. I don't have access to a coach and really don't know what to do. I also thought that there must be a better way of comparing each pair, but had no success.

Since we want to check for all pairs of numbers having the same GCD, we can assume the GCD of any pair of numbers is this common GCD and then verify that assumption. It is simple to take the GCD of the first two numbers (which are guaranteed to exist since N is at least 2).

Then, if any element of the array is not divisible by this GCD, the answer is "NO". After this check, we can divide every element by the presumed GCD and inspect the factors of this quotient. If more than one element has the same prime factor, then the answer is also "NO" since the GCD of at least two elements would be larger than the presumed GCD by at least a factor of that prime.

Sample implementation:

#include <iostream>
#include <vector>
#include <numeric>
int main() {
    int N;
    std::cin >> N;
    std::vector<int> vals(N);
    for (int& x : vals) std::cin >> x;
    int gcd = std::gcd(vals[0], vals[1]);
    std::vector<bool> seenFactor(1e7 + 1);
    for (int x : vals) {
        if (x % gcd) {
            std::cout << "NO\n";
            return 0;
        }
        x /= gcd;
        for (int d = 2; d * d <= x; ++d) {
            if (x % d == 0) {
                if (seenFactor[d]) {
                    std::cout << "NO\n";
                    return 0;
                }
                seenFactor[d] = true;
                while (x % d == 0) x /= d;
            }
        }
        if (x > 1) {
            if (seenFactor[x]) {
                std::cout << "NO\n";
                return 0;
            }
            seenFactor[x] = true;
        }
    }
    std::cout << "YES\n";
}