xをn乗した数をmで割った余りを求める

使いどころ

• b進数で表したときの下n桁を求める

単純版 O(n)

int mod_pow(int x, int n, int m){
    int r = 1;
    while(n--){
        r *= x;
        r %= m;
    }
    return r;
}

高速版 O(logn)

#include <bitset>

int mod_pow(int x, int n, int m){
    int r = 1;
    bitset<64> bs(n);
    for(int i = 0; i < 64; i++){
        x %= m;
        if(bs[i]) r = (r * x)%m; 
        x *= x;
    }
    return r;
}