桁数を抑えたバイナリ法

普通のバイナリ法

// バイナリ法
// a^n mod m
fn pow_mod(mut a: usize, mut n: usize, m: usize) -> usize {
    let mut res: usize = 1;
    while n > 0 {
        if n & 1 == 1 {
            res = res * a % m;
        }
        a = a * a % m;
        n >>= 1;
    }
    res
}

桁数を抑えたバイナリ法

桁数を底の２乗以下に抑えます

fn pow_mod2(a: usize, mut n: usize, mk: usize) -> usize {
    let mut m = a;
    let mut ans = 1;
    let mut sf = true;
    while n > 0 {
        if sf {
            sf = false;
        } else {
            m = m * m % mk;
        }
        if n & 1 == 1 {
            ans = m * ans % mk;
        }
        println!("{} {} {}", n & 1, m, ans);
        n >>= 1;
    }
    ans
}