AtotheNmodM

AtotheNmodM

medium

Given natural numbers \(A, N\), and \(M\). Determine whether the number \(A^N\) is divisible by \(M\).

Note: Pay attention that the number \(A^N\) can be extremely large - it is recommended to factorize numbers \(A\) and \(M\) and analyze their prime factors!

Input:

• The first and only line of standard input contains, in order, the natural numbers \(A, N\), and \(M\).

Output:

• Print “YES” if the number \(A^N\) is divisible by \(M\), otherwise print “NO”.

Constraints:

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

If this task is too hard for you, try solving it when * \(A\) and \(M\) are both powers of two

Or, if it’s still too hard, try solving it when * \(1 \leq N \leq 2\)

Example:

Input:

10 2 50

Output:

YES

Solution

The number (A^N) can be astronomically large, so we must not compute it directly.

Factorize:

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

Let (v_i = v_{p_i}(A)) be the exponent of prime (p_i) in (A).
Then in (A^N), the exponent becomes:

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

So:

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

The algorithm is then:

1. If \(M = 1\): answer YES.
2. Factorize \(M\) into prime powers \(p^e\).
3. For each prime \(p^e\) in \(M\):
   • Count how many times \(p\) divides \(A\), call it \(v\).
   • If \(v = 0\): \(A^N\) has no \(p\), so answer NO.
   • Otherwise check \(N\cdot v \ge e\).
     To avoid overflow, use: \[N \ge \left\lceil \frac{e}{v} \right\rceil\]
4. If all prime powers pass, answer YES, else NO.

Complexity:

• Factorization by trial division: \(O(\sqrt{M})\)
• For each prime factor, counting exponent in \(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;
}