counting-divisors

Counting Divisors

CSES medium

يُعطى لك \(n\) عددًا صحيحًا. لكل منها، أوجد عدد قواسمه. مثلًا للعدد \(18\) عدد \(6\) قواسم: \(1, 2, 3, 6, 9, 18\).

القيود:

\(1 \le n \le 10^5\)
\(1 \le x \le 10^6\)

الإدخال:

السطر الأول: عدد صحيح \(n\).
الأسطر الـ \(n\) التالية: عدد صحيح \(x\) في كل سطر.

المخرجات:

لكل عدد، سطر فيه عدد قواسمه.

مثال:

الإدخال:

المخرجات:

5
2
6

الحل

عدّ قواسم كل عدد بطريقة \(O(\sqrt{x})\) يستغرق حتى \(10^5 \cdot 10^3 = 10^8\) خطوة. توجد طريقة أسرع.

إذا كان التحليل إلى العوامل الأولية للعدد \(x\) هو

\[ x = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}, \]

فإن كل قاسم للعدد \(x\) هو \(p_1^{f_1} \cdot p_2^{f_2} \cdots p_k^{f_k}\) مع \(0 \le f_i \le e_i\). لكل أسّ \(f_i\) يوجد \(e_i + 1\) اختيارًا، لذلك حسب قاعدة الضرب يكون عدد القواسم

\[ (e_1 + 1) \cdot (e_2 + 1) \cdots (e_k + 1). \]

مثلًا \(18 = 2^1 \cdot 3^2\) له \((1 + 1) \cdot (2 + 1) = 6\) قواسم.

نحلّل كل عدد باستخدام غربال أصغر عامل أولي (SPF) من درس التحليل إلى العوامل الأولية. يُحسب الغربال مرة واحدة في زمن \(O(\text{MAXN} \log \log \text{MAXN})\)، ثم يستغرق كل تحليل \(O(\log x)\).

#include <iostream>
using namespace std;

const int MAXN = 1000000;
int spf[MAXN + 1];

void sieve() {
    // Initialize: smallest prime factor of i is i itself
    for (int i = 1; i <= MAXN; i++) spf[i] = i;

    for (int i = 2; i * i <= MAXN; i++) {
        if (spf[i] == i) {  // If i is prime
            for (int j = i * i; j <= MAXN; j += i) {
                // Mark smallest factor for j if not marked yet
                if (spf[j] == j) {
                    spf[j] = i;
                }
            }
        }
    }
}

int count_divisors(int x) {
    int result = 1;
    while (x != 1) {
        int p = spf[x];

        // e = the exponent of p in x
        int e = 0;
        while (x % p == 0) {
            x /= p;
            e++;
        }

        result *= e + 1;
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    sieve();

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cout << count_divisors(x) << "\n";
    }
}