Deep Dive into the Extended Euler's Theorem and Its Application in Large Exponent Modulo Reduction

Core Logic and Mathematical Principles

1. Mathematical Properties of Euler's Function

Euler's function $\varphi(N)$ represents the count of integers $i$ satisfying $1 \le i \le N$ and $\gcd(i, N) = 1$. Besides the linear sieve method for recursion, it possesses the following core properties in number theory:

Property 1: If $p$ is a prime, then $\varphi(p) = p - 1$; if $k \ge 1$, then $\varphi(p^k) = p^k - p^{k-1} = p^k \left(1 - \frac{1}{p}\right)$.
Property 2 (Dirichlet Convolution Expansion): The sum of the Euler's function of all divisors of a positive integer $N$ equals the integer itself, namely:

$$\sum_{d \mid N} \varphi(d) = N$$

Property 3: The algebraic sum of all integers less than or equal to $N$ that are coprime to $N$ is:

$$S = \frac{N \cdot \varphi(N)}{2} \quad (N > 1)$$

2. Euler's Theorem

If the positive integer $a$ is coprime to $m$ (i.e., $\gcd(a, m) = 1$), then:

$$a^{\varphi(m)} \equiv 1 \pmod m$$

When $m$ is prime, $\varphi(m) = m - 1$, and the theorem reduces to Fermat's Little Theorem: $a^{m-1} \equiv 1 \pmod m$.

3. Extended Euler's Theorem (Large Exponent Reduction Formula)

In NOIP competitions, one often encounters the problem of calculating $a^b \bmod m$, where the base $a$ and modulus $m$ are within normal ranges, but the exponent $b$ is extremely large (for example, $b \le 10^{2000000}$, given as a string). Since we cannot directly perform $b \bmod m$ (which is a common mathematical error among beginners), we must use the Extended Euler's Theorem for exponent reduction.

This theorem does not require $a$ to be coprime to $m$, making it universal: $$a^b \equiv \begin{cases} a^{b \bmod \varphi(m)} \pmod m & \gcd(a, m) = 1 \ a^b \pmod m & \gcd(a, m) \neq 1 \text{ and } b < \varphi(m) \ a^{(b \bmod \varphi(m)) + \varphi(m)} \pmod m & \gcd(a, m) \neq 1 \text{ and } b \ge \varphi(m) \end{cases}$$

State Design and Algorithm Derivation

State Design for Single Large Exponent Reduction

For extremely large exponent $b$, we cannot store it in any native integer type. We must use single-character streaming input (a variant of fast reading) for dynamic exponent reduction.
During the reading and transforming process, we need to maintain two layers of state:

Value Dimension: The current value of the exponent modulo $\varphi(m)$.
State Dimension: Whether the current true exponent value has exceeded $\varphi(m)$.

Define a boolean flag over_limit. Let the currently read number form the value $b'$, when reading the next digit $d$:

$$b_{\text{new}}' = b' \cdot 10 + d$$

If at any moment $b_{\text{new}}' \ge \varphi(m)$, set over_limit = true and force:

$$b_{\text{new}}' = (b' \cdot 10 + d) \bmod \varphi(m)$$

Finally, if over_limit is true, the final exponent for fast power will be $b' + \varphi(m)$; otherwise, it will be directly $b'$. This allows us to compress an exponent of size $O(10^{2000000})$ to $O(M)$ level instantly.

C++ Standard Source Code

#include <iostream>
#include <string>

// Single-point calculation of Euler's function phi(m), time complexity O(\sqrt{m})
long long get_phi(long long m) {
    long long ans = m;
    long long temp = m;
    for (long long i = 2; i * i <= temp; ++i) {
        if (temp % i == 0) {
            ans = ans / i * (i - 1); // Divide first, then multiply to avoid truncation and overflow
            while (temp % i == 0) temp /= i;
        }
    }
    if (temp > 1) {
        ans = ans / temp * (temp - 1);
    }
    return ans;
}

// Fast power with modulus base
long long quick_power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = (__int128_t)res * base % mod; // __int128_t to prevent overflow during multiplication
        base = (__int128_t)base * base % mod;
        exp >>= 1;
    }
    return res;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long a, m;
    if (std::cin >> a >> m) {
        long long phi_m = get_phi(m);
        long long b = 0;
        bool over_limit = false;

        char ch;
        // Filter leading non-digit characters
        while (std::cin >> ch && (ch < '0' || ch > '9'));

        // Dynamically read large numbers and execute extended Euclidean exponent reduction determination
        while (ch >= '0' && ch <= '9') {
            b = b * 10 + (ch - '0');
            if (b >= phi_m) {
                over_limit = true;
                b %= phi_m;
            }
            // Attempt to read the next character; if not a digit, safely terminate
            if (!(std::cin >> ch)) break; 
        }

        // Assemble the final exponent state based on theorem boundary conditions
        long long final_exp = b;
        if (over_limit) {
            final_exp += phi_m;
        }

        long long ans = quick_power(a, final_exp, m);
        std::cout << ans << "\n";
    }
    return 0;
}

NOIP Practical Pitfall Guide

Incorrect traditional modulo operation when reading large exponent
Some contestants mistakenly wrote b = (b * 10 + ch - '0') % m while reading the extremely large exponent $b$. Note: The exponent must be modulo $\varphi(m)$, not $m$. Once confused, the computed answer will be completely unrelated to the correct result.
Ignoring additive offset destruction of properties when $b < \varphi(m)$
The extended Euclidean theorem clearly states that only when $b \ge \varphi(m)$ can the exponent apply $b \bmod \varphi(m) + \varphi(m)$. If $b$ itself is very small (for example, $b = 1$), and you blindly added $\varphi(m)$, when $\gcd(a, m) \neq 1$, the result calculated will be multiplied by several factors more than the original version, leading to logical failure. The over_limit flag must be used to strictly branch.