modular-arithmetic/binpow.hpp

• View this file on GitHub
• Last update: 2026-04-04 10:38:14+05:30
• Include: #include "modular-arithmetic/binpow.hpp"

Required by

• polynomial/formal-power-series.hpp
• polynomial/ntt.hpp

Verified with

• verify/yosupo/convolution/convolution_mod.test.cpp
• verify/yosupo/polynomial/exp_of_formal_power_series.test.cpp
• verify/yosupo/polynomial/inv_of_formal_power_series.test.cpp
• verify/yosupo/polynomial/log_of_formal_power_series.test.cpp
• verify/yosupo/polynomial/pow_of_formal_power_series.test.cpp

Code

#pragma once

/**
 * Author: Teetat T.
 * Date: 2024-01-15
 * Description: n-th power using divide and conquer
 * Time: $O(\log b)$
 */

template<class T>
constexpr T binpow(T a,ll b){
    T res=1;
    for(;b>0;b>>=1,a*=a)if(b&1)res*=a;
    return res;
}

#line 2 "modular-arithmetic/binpow.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-01-15
 * Description: n-th power using divide and conquer
 * Time: $O(\log b)$
 */

template<class T>
constexpr T binpow(T a,ll b){
    T res=1;
    for(;b>0;b>>=1,a*=a)if(b&1)res*=a;
    return res;
}

Back to top page