Common Divisors

Common Divisors
Codeforces medium

You are given an array \(a\) of \(n\) integers. Find the number of positive integers \(x\) that divide every element of the array.

Constraints:

  • \(1 \le n \le 4 \cdot 10^5\)
  • \(1 \le a_i \le 10^{12}\)

Input:

  • First line: integer \(n\).
  • Second line: \(n\) integers \(a_1, a_2, \dots, a_n\).

Output:

  • One integer — the number of common divisors of all elements.

Example:

Input:

6
6 90 12 18 30 18

Output:

4

(The common divisors are \(1\), \(2\), \(3\), and \(6\).)

Solution

A number divides all elements of the array exactly when it divides their greatest common divisor. So the answer is the number of divisors of

\[ g = \gcd(a_1, a_2, \dots, a_n). \]

We compute \(g\) step by step: \(\gcd(a_1, a_2, a_3) = \gcd(\gcd(a_1, a_2), a_3)\), and so on. We start with \(g = 0\), because \(\gcd(0, x) = x\).

Then we count the divisors of \(g\) with the \(O(\sqrt{g})\) method from the lesson on divisors: each divisor \(i \le \sqrt{g}\) comes with the partner \(g / i\), and we count the partner only if it is different from \(i\).

\(g \le 10^{12}\), so the loop makes at most \(10^6\) steps. The values reach \(10^{12}\), so we use long long, also in the gcd function.

#include <iostream>
using namespace std;

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

int main() {
    int n;
    cin >> n;

    long long g = 0;  // gcd(0, x) = x
    for (int i = 0; i < n; i++) {
        long long a;
        cin >> a;
        g = gcd(g, a);
    }

    // count the divisors of g
    int divisors = 0;
    for (long long i = 1; i * i <= g; i++) {
        if (g % i == 0) {
            divisors++;           // the small divisor i
            if (i != g / i) {
                divisors++;       // its partner g / i
            }
        }
    }

    cout << divisors << "\n";
}