An important observation is \(\gcd(x,y)\leq\min(x,y)\). So the minimum of all numbers \(\min{A_i}\) proves to be the maximum answer we could get.

Since all the possible answers must be a factor of some number in the array, we can find the factors of every number within \(\mathcal{O}(N\sqrt{\max{A_i}})\) iterations.

Not all factors can be the final answer. Supposing that a factor \(k<\min{A_i}\) can be the final answer,

• \(k\) must be a factor of some number \(A_i\).
• \(k\) comes from a series \(\gcd\) operations, e.g., \(\gcd(A_{p_1},A_{p_2},\dots)\). \(k\) cannot be \(A_i\) itself since we have \(k<\min{A_i}\).
• Since the order of \(\gcd\) operations does not matter, the first time we meet \(k\), supposing that we are dealing with the number \(A_i\), we can set \(memo[k]\) to \(A_i\). Note that here we have \(memo[k]\geq k\).
• Our goal is to get \(k\) in the end (\(memo[k]=k\)), so each time we have the chance to perform a \(\gcd\) operation (meaning that \(k\) is also a factor of some other number \(A_j\)), we should perform the \(\gcd\) operation to reduce the number \(memo[k]\) to \(\gcd(memo[k],A_j)\). Since both \(memo[k]\) and \(A_j\) can be divided by \(k\), it is assured that \(memo[k]\) can be divided by \(k\). We do the \(\gcd\) operation whenever possible because \(\gcd(x,y)\leq\min(x,y)\), and we want to reduce the value \(memo[k]\).

After processing all the numbers, we check our \(memo\) and count for how many factors \(memo[k]=k\) holds.

And the final answer would be that count plus \(1\) (by using \(\min\) operations only).

• Time complexity is \(\mathcal{O}(N\sqrt{\max{A_i}}\log{\max{A_i}})\).
• Space complexity is \(\mathcal{O}(Nd)\), where \(d\) is the maximum number of factors of a single number.

Code (C++)

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;
int main() {
  int n;
  cin >> n;

  vector<int> a(n);
  for (int i = 0; i < n; ++i)
    cin >> a[i];
  int lo = *min_element(a.begin(), a.end());

  unordered_map<int, int> memo;
  for (int ai : a) {
    for (int j = 1; j * j <= ai && j < lo; ++j) {
      if (ai % j == 0) {
        memo[j] = __gcd(ai, memo[j]);
        if (ai / j < lo)
          memo[ai / j] = __gcd(ai, memo[ai / j]);
      }
    }
  }

  int ans = 1;
  for (auto [factor, terminal] : memo)
    if (factor == terminal)
      ans++;

  cout << ans;
}

Code (Rust)

use proconio::input;
use std::collections::HashMap;

fn gcd(x: usize, y: usize) -> usize {
    if y == 0 {
        x
    } else {
        gcd(y, x % y)
    }
}

fn main() {
    input! {
        n: usize,
        a: [usize; n],
    }

    let mut factors: HashMap<usize, usize> = HashMap::new();
    let lo = *a.iter().min().unwrap();

    for i in 0..n {
        for j in 1..lo {
            if j * j > a[i] {
                break;
            }

            if a[i] % j == 0 {
                let original = *factors.entry(j).or_insert(a[i]);
                factors.insert(j, gcd(original, a[i]));
                if a[i] / j < lo {
                    let original = *factors.entry(a[i] / j).or_insert(a[i]);
                    factors.insert(a[i] / j, gcd(original, a[i]));
                }
            }
        }
    }

    let mut ans = 1;
    for (original, terminal) in factors {
        if original == terminal {
            ans += 1;
        }
    }

    println!("{}", ans);
}