haar_lib/math/mod_ops/
pow.rs

1//! xᵖ (mod m)を求める。
2
3/// xᵖ (mod m)を求める。
4///
5/// **Time complexity** $O(\log p)$
6#[inline]
7pub fn mod_pow(mut x: u64, mut p: u64, m: u64) -> u64 {
8    let mut ret = 1;
9    while p > 0 {
10        if (p & 1) != 0 {
11            ret *= x;
12            ret %= m;
13        }
14        x *= x;
15        x %= m;
16
17        p >>= 1;
18    }
19    ret
20}