src/modular-arithmetic/binpow.hpp

• View this file on GitHub
• Last update: 2025-07-19 15:28:18+09:00
• Include: #include "src/modular-arithmetic/binpow.hpp"

Required by

• src/polynomials/formal-power-series.hpp
• Multipoint Evaluation (src/polynomials/multipoint-evaluation.hpp)
• src/polynomials/ntt.hpp

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 "src/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