Math/pow_mod.hpp

• View this file on GitHub
• Last update: 2023-04-05 23:10:22+09:00
• Include: #include "Math/pow_mod.hpp"

Required by

• 離散対数 (log mod) (Math/log_mod.hpp)

Verified with

• test/yosupo_DiscreteLog.test.cpp

Code

// a^n (mod m)
ll pow_mod(ll a,ll n,ll m){
    ll ret=1;
    while(n){
        if(n&1) ret=ret*a%m;
        a=(a*a)%m;
        n/=2;
    }
    return ret;
}

#line 1 "Math/pow_mod.hpp"
// a^n (mod m)
ll pow_mod(ll a,ll n,ll m){
    ll ret=1;
    while(n){
        if(n&1) ret=ret*a%m;
        a=(a*a)%m;
        n/=2;
    }
    return ret;
}

Back to top page