common-divisors

Common Divisors

Codeforces medium

يُعطى لك مصفوفة \(a\) من \(n\) أعداد صحيحة. أوجد عدد الأعداد الصحيحة الموجبة \(x\) التي تقسم كل عناصر المصفوفة.

القيود:

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

الإدخال:

السطر الأول: عدد صحيح \(n\).
السطر الثاني: \(n\) عددًا \(a_1, a_2, \dots, a_n\).

المخرجات:

عدد صحيح واحد — عدد القواسم المشتركة لكل العناصر.

مثال:

الإدخال:

6
6 90 12 18 30 18

المخرجات:

(القواسم المشتركة هي \(1\) و \(2\) و \(3\) و \(6\).)

الحل

يقسم العدد كل عناصر المصفوفة تمامًا عندما يقسم القاسم المشترك الأكبر لها. لذلك الجواب هو عدد قواسم

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

نحسب \(g\) خطوة بعد خطوة: \(\gcd(a_1, a_2, a_3) = \gcd(\gcd(a_1, a_2), a_3)\)، وهكذا. نبدأ بالقيمة \(g = 0\)، لأن \(\gcd(0, x) = x\).

ثم نعدّ قواسم \(g\) بطريقة \(O(\sqrt{g})\) من درس القواسم: كل قاسم \(i \le \sqrt{g}\) يأتي مع شريكه \(g / i\)، ونعدّ الشريك فقط إذا كان مختلفًا عن \(i\).

بما أن \(g \le 10^{12}\)، فإن الحلقة تُجري \(10^6\) خطوة على الأكثر. تصل القيم إلى \(10^{12}\)، لذلك نستخدم long long، وكذلك في الدالة gcd.

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