1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

//! 累乗剰余
pub fn modpow(base: i64, exp: i64, n: i64) -> i64 {
    let (mut base, mut exp, n) = (base as u128, exp, n as u128);

    assert!(
        exp >= 0,
        "negative exponent cannot be used in modular exponentiation"
    );

    if exp == 0 {
        return 1;
    }

    let mut res = 1;
    base %= n;

    loop {
        if exp % 2 == 1 {
            res *= &base;
            res %= &n;
        }

        if exp == 1 {
            return res as i64;
        }

        exp /= 2;
        base *= base;
        base %= n;
    }
}

#[cfg(test)]
mod tests {
    use super::modpow;

    #[test]
    fn test_modpow() {
        assert_eq!(modpow(3, 5, 5), 3);
        assert_eq!(modpow(2, 32, 9), 4);
    }
}