This documentation is automatically generated by online-judge-tools/verification-helper
#include "ugilib/math/pow.hpp"
#pragma once
#include <bits/stdc++.h>
#include "ugilib/base/definitions.hpp"
namespace ugilib {
/**
* @brief 繰り返し二乗法
* @param x 基数
* @param n 指数
* @param mod mod
* @return x^n % mod
* @note O(log n)
*/
template <typename T>
T fast_pow(T x, ll n, T mod = ugilib::constants::INF<T>) {
assert(n >= 0);
T res = 1;
while (n) {
if (n & 1) res = res*x % mod;
x = x*x % mod;
n >>= 1;
}
return res;
}
} // namespace ugilib
#line 2 "ugilib/math/pow.hpp"
#include <bits/stdc++.h>
#line 2 "ugilib/base/definitions.hpp"
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i, n) for(size_t i = 0; i < n; i++) // rep macro
#define all(v) begin(v), end(v) // all iterator
#line 4 "ugilib/math/pow.hpp"
namespace ugilib {
/**
* @brief 繰り返し二乗法
* @param x 基数
* @param n 指数
* @param mod mod
* @return x^n % mod
* @note O(log n)
*/
template <typename T>
T fast_pow(T x, ll n, T mod = ugilib::constants::INF<T>) {
assert(n >= 0);
T res = 1;
while (n) {
if (n & 1) res = res*x % mod;
x = x*x % mod;
n >>= 1;
}
return res;
}
} // namespace ugilib