Efficient computation of $a^b \bmod m$ utilizes the binary representation of the exponent $b$. By expressing $b$ as $\sum_{i=0}^{k} c_i \cdot 2^i$ where $c_i \in {0,1}$, the power decomposes into a product of squared terms: $a^b = \prod_{i=0}^{k} (a^{2^i})^{c_i}$.

The algorithm iterates through each bit of $b$ from least to most signiifcant. The bitwise AND operation (& 1) isolates the current bit $c_i$, determining whether to incorporate $a^{2^i}$ into the cumulative result. Simultaneous, the right shift operator (>>= 1) advances to the next bit by dividing $b$ by 2, while squaring the base prepares $a^{2^{i+1}}$ for the subsequent iteration.

#include <cstdio>
typedef long long int64;

int64 mod_power(int64 base, int64 exponent, int64 modulus) {
    int64 product = 1 % modulus;
    while (exponent) {
        if (exponent & 1LL)
            product = product * base % modulus;
        base = base * base % modulus;
        exponent >>= 1;
    }
    return product;
}

int main() {
    int cases;
    scanf("%d", &cases);
    while (cases--) {
        int64 a, b, p;
        scanf("%lld%lld%lld", &a, &b, &p);
        printf("%lld\n", mod_power(a, b, p));
    }
    return 0;
}

When the modulus $p$ is prime, Fermat's Little Theorem provides a method to compute modular multiplicative inverses. For an integer $a$ not divisible by $p$, the theorem states $a^{p-1} \equiv 1 \pmod{p}$. Rearranging gives $a \cdot a^{p-2} \equiv 1 \pmod{p}$, establishing that $a^{p-2} \bmod p$ is the multiplicative inverse of $a$.

This reduces the inverse calculation to another instance of binary exponentiation. The inverse exists if and only if $\gcd(a,p) = 1$; for prime $p$, this requires $a \not\equiv 0 \pmod{p}$.

#include <cstdio>
typedef long long int64;

int64 binary_exp(int64 base, int64 exp, int64 mod) {
    int64 res = 1;
    while (exp > 0) {
        if (exp & 1LL) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        int64 a, p;
        scanf("%lld%lld", &a, &p);
        if (a % p == 0)
            printf("impossible\n");
        else
            printf("%lld\n", binary_exp(a, p - 2, p));
    }
    return 0;
}

Bitwise shift operations provide efficient arithmetic primitives. A left shift (<< n) multiplies by $2^n$ by appending $n$ zeros to the binary representation, while a right shift (>> n) performs integer division by $2^n$ by removing the $n$ least significent bits. These operations execute in constant time and form the basis of the logarithmic exponentiation algorithm.