Common Divisors
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";
}