Refactoring: Binary Exponentiation

C++ — generic template

template<typename T>
T mod_pow(T base, T exp, T mod) {
    T result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

// Works with int, long long, etc.
cout << mod_pow(3LL, 10LL, MOD) << "\n";

Rust — generic

fn mod_pow<T>(mut base: T, mut exp: T, m: T) -> T
where
    T: std::ops::Rem<Output = T>
      + std::ops::Mul<Output = T>
      + std::ops::ShrAssign<T>
      + std::ops::BitAnd<T, Output = T>
      + Copy + From<u8> + PartialOrd,
{
    let one = T::from(1);
    let mut result = T::from(1);
    base = base % m;
    while exp > one {
        if (exp & one) == one {
            result = (result * base) % m;
        }
        base = (base * base) % m;
        exp >>= one;
    }
    result
}

In practice, just write the u64 version — generics are verbose in Rust for this.

C++

long long mod_pow_rec(long long a, long long b, long long m) {
    if (b == 0) return 1;
    long long half = mod_pow_rec(a, b / 2, m);
    half = (half * half) % m;
    if (b % 2 == 1) half = (half * a) % m;
    return half;
}

Rust

fn mod_pow_rec(a: u64, b: u64, m: u64) -> u64 {
    if b == 0 { return 1; }
    let half = mod_pow_rec(a, b / 2, m);
    let half = (half * half) % m;
    if b % 2 == 1 { (half * a) % m } else { half }
}