cp_library_rs/number_theory/powmod.rs
1//! あまりを取る累乗
2
3/// あまりをとる累乗
4///
5/// **戻り値**
6/// - `usize` : $`a^b \mod m`$
7///
8/// **計算量**
9/// - $`O(\log b)`$
10pub fn powmod(mut a: usize, mut b: usize, m: usize) -> usize {
11 let mut res = 1;
12 while b > 0 {
13 if b & 1 == 1 {
14 res = (res * a) % m;
15 }
16 a %= m;
17 a = (a * a) % m;
18 b >>= 1;
19 }
20 res
21}