dsalgo/
modular_power_recurse_i64.rs

1pub fn pow(
2    modulus: i64,
3    mut x: i64,
4    n: i64,
5) -> i64 {
6    x %= modulus;
7
8    if n == 0 {
9        return 1;
10    }
11
12    let mut y = pow(modulus, x, n >> 1);
13
14    y = y * y % modulus;
15
16    if n & 1 == 1 {
17        y = y * x % modulus;
18    }
19
20    y
21}
22
23#[cfg(test)]
24
25mod tests {
26
27    use super::*;
28
29    #[test]
30
31    fn test() {
32        let m = 1_000_000_007;
33
34        let inv_2 = (m + 1) >> 1;
35
36        assert_eq!(pow(m, 2, m - 2), inv_2);
37    }
38}