AtotheNmodM

AtotheNmodM

medium

لديك الأعداد الطبيعية \(A, N\) و\(M\). حدّد ما إذا كان العدد \(A^N\) يقبل القسمة القسمة على \(M\).

ملاحظة: انتبه إلى أن العدد \(A^N\) قد يكون ضخمًا جدًا — يُنصح بتحليل العددين \(A\) و\(M\) إلى عواملهما الأولية ودراسة عواملهما الأولية!

المدخلات:

• السطر الأول والوحيد يحتوي، بالترتيب، على الأعداد الطبيعية \(N, M\) و\(A\).

المخرجات:

• اطبع “YES” إذا كان العدد \(A^N\) يقبل القسمة على \(M\)، وإلا اطبع “NO”.

المحددات:

• \(1 \leq A, N, M \leq 10^9\)

إذا كانت هذه المسألة صعبة جدًا عليك، فحاول حلّها عندما * يكون كل من \(A\) و\(M\) قوتين للعدد 2

أو، إذا كانت لا تزال صعبة جدًا، فحاول حلّها عندما * \(1 \leq N \leq 2\)

مثال:

مدخل:

50 2 10

مخرج:

YES

Solution

العدد \(A^N\) قد يكون ضخمًا بشكل فلكي، لذلك يجب ألا نحسبه مباشرة.

حلّل إلى عوامل أولية:

\[M = \prod p_i^{e_i}\]

ليكن \(v_i = v_{p_i}(A)\) هو أسّ العدد الأولي \(p_i\) في \(A\).
عندئذٍ في \(A^N\) يصبح الأسّ:

\[v_{p_i}(A^N) = N \cdot v_{p_i}(A)\]

إذًا:

\[M \mid A^N \iff \forall i:\; N\cdot v_{p_i}(A)\ge e_i\]

وعليه تكون الخوارزمية كما يلي:

1. إذا كان \(M = 1\): فالجواب YES.
2. حلّل \(M\) إلى قوى أولية \(p^e\).
3. لكل عدد أولي \(p^e\) في \(M\):
   • احسب عدد المرات التي يقسم فيها \(p\) العدد \(A\)، ولنسمّه \(v\).
   • إذا كان \(v = 0\)، فإن \(A^N\) لا يحتوي على \(p\)، إذًا الجواب NO.
   • وإلا تحقّق من أن \(N\cdot v \ge e\).
     لتجنّب تجاوز السعة المستخدمة، استخدم: \[N \ge \left\lceil \frac{e}{v} \right\rceil\]
4. إذا تحققت جميع الشروط للقوى الأولية، فالجواب YES، وإلا NO.

درجة التعقية:

• التحليل إلى عوامل أولية باستخدام القسمة التجريبية: \(O(\sqrt{M})\)
• ولكل عامل أولي، حساب الأسّ في \(A\): \(O(\log A)\)

#include <iostream>

using namespace std;

long long ceil_div(long long a, long long b) {
    // b > 0
    return (a + b - 1) / b;
}

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

    long long A, N, M;
    cin >> A >> N >> M;

    if (M == 1) {
        cout << "YES\n";
        return 0;
    }

    long long m = M;

    // Factorize M: m = product p^e
    for (long long p = 2; p * p <= m; ++p) {
        if (m % p != 0) 
            continue;

        long long e = 0;
        while (m % p == 0) {
            m /= p;
            e++;
        }

        // Compute v_p(A)
        long long v = 0;
        long long tempA = A;
        while (tempA % p == 0) {
            tempA /= p;
            v++;
        }

        if (v == 0) {
            cout << "NO\n";
            return 0;
        }

        // Need N * v >= e  <=>  N >= ceil(e / v)
        long long need = ceil_div(e, v);
        if (N < need) {
            cout << "NO\n";
            return 0;
        }
    }

    // If remaining m > 1, it's a prime factor with exponent 1
    if (m > 1) {
        long long p = m;
        long long e = 1;

        long long v = 0;
        long long tempA = A;
        while (tempA % p == 0) {
            tempA /= p;
            v++;
        }

        if (v == 0) {
            cout << "NO\n";
            return 0;
        }

        long long need = ceil_div(e, v); // e=1 => need=1 always if v>=1
        if (N < need) {
            cout << "NO\n";
            return 0;
        }
    }

    cout << "YES\n";
    return 0;
}