math/monoid/pow.hpp

• View this file on GitHub
• Last update: 2025-04-05 12:46:42+09:00
• Include: #include "math/monoid/pow.hpp"

Required by

• math/monoid/bsgs.hpp

Code

#ifndef KK2_MATH_MONOID_POW_HPP
#define KK2_MATH_MONOID_POW_HPP 1

namespace kk2 {

namespace monoid {

template <class M> M pow(M a, long long n) {
    M res = M::unit();
    while (n > 0) {
        if (n & 1) res = M::op(res, a);
        if (n >>= 1) a = M::op(a, a);
    }
    return res;
}

} // namespace monoid

} // namespace kk2

#endif // KK2_MATH_MONOID_POW_HPP

#line 1 "math/monoid/pow.hpp"



namespace kk2 {

namespace monoid {

template <class M> M pow(M a, long long n) {
    M res = M::unit();
    while (n > 0) {
        if (n & 1) res = M::op(res, a);
        if (n >>= 1) a = M::op(a, a);
    }
    return res;
}

} // namespace monoid

} // namespace kk2

Back to top page