#line 2 "include/e6nlaq/math/acl.hpp"
// This file is a fork of AtCoder Library.
#define E6NLAQ_MATH_ACL_HPP
#include <algorithm>
#include <cassert>
#include <tuple>
#include <vector>
#line 2 "include/e6nlaq/internal/math.hpp"
// This file is a fork of AtCoder Library.
#define E6NLAQ_INTERNAL_MATH_HPP
#include <utility>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace e6nlaq {
namespace internal {
// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
unsigned int _m;
unsigned long long im;
// @param m `1 <= m`
explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
// @return m
unsigned int umod() const { return _m; }
// @param a `0 <= a < m`
// @param b `0 <= b < m`
// @return `a * b % m`
unsigned int mul(unsigned int a, unsigned int b) const {
// [1] m = 1
// a = b = im = 0, so okay
// [2] m >= 2
// im = ceil(2^64 / m)
// -> im * m = 2^64 + r (0 <= r < m)
// let z = a*b = c*m + d (0 <= c, d < m)
// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
// ((ab * im) >> 64) == c or c + 1
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned long long y = x * _m;
return (unsigned int)(z - y + (z < y ? _m : 0));
}
};
// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a : bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n>
constexpr bool is_prime = is_prime_constexpr(n);
// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
// Contracts:
// [1] s - m0 * a = 0 (mod b)
// [2] t - m1 * a = 0 (mod b)
// [3] s * |m1| + t * |m0| <= b
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
// [3]:
// (s - t * u) * |m1| + t * |m0 - m1 * u|
// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
// = s * |m1| + t * |m0| <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
// by [3]: |m0| <= b/g
// by g != b: |m0| < b/g
if (m0 < 0) m0 += b / s;
return {s, m0};
}
// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m>
constexpr int primitive_root = primitive_root_constexpr(m);
// @param n `n < 2^32`
// @param m `1 <= m < 2^32`
// @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64)
unsigned long long floor_sum_unsigned(unsigned long long n,
unsigned long long m,
unsigned long long a,
unsigned long long b) {
unsigned long long ans = 0;
while (true) {
if (a >= m) {
ans += n * (n - 1) / 2 * (a / m);
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
unsigned long long y_max = a * n + b;
if (y_max < m) break;
// y_max < m * (n + 1)
// floor(y_max / m) <= n
n = (unsigned long long)(y_max / m);
b = (unsigned long long)(y_max % m);
std::swap(m, a);
}
return ans;
}
} // namespace internal
} // namespace e6nlaq
#line 13 "include/e6nlaq/math/acl.hpp"
namespace e6nlaq {
inline long long pow_mod(long long x, long long n, int m) {
assert(0 <= n && 1 <= m);
if (m == 1) return 0;
internal::barrett bt((unsigned int)(m));
unsigned int r = 1, y = (unsigned int)(internal::safe_mod(x, m));
while (n) {
if (n & 1) r = bt.mul(r, y);
y = bt.mul(y, y);
n >>= 1;
}
return r;
}
inline long long inv_mod(long long x, long long m) {
assert(1 <= m);
auto z = internal::inv_gcd(x, m);
assert(z.first == 1);
return z.second;
}
// (rem, mod)
inline std::pair<long long, long long> crt(const std::vector<long long>& r,
const std::vector<long long>& m) {
assert(r.size() == m.size());
int n = int(r.size());
// Contracts: 0 <= r0 < m0
long long r0 = 0, m0 = 1;
for (int i = 0; i < n; i++) {
assert(1 <= m[i]);
long long r1 = internal::safe_mod(r[i], m[i]), m1 = m[i];
if (m0 < m1) {
std::swap(r0, r1);
std::swap(m0, m1);
}
if (m0 % m1 == 0) {
if (r0 % m1 != r1) return {0, 0};
continue;
}
// assume: m0 > m1, lcm(m0, m1) >= 2 * max(m0, m1)
// (r0, m0), (r1, m1) -> (r2, m2 = lcm(m0, m1));
// r2 % m0 = r0
// r2 % m1 = r1
// -> (r0 + x*m0) % m1 = r1
// -> x*u0*g = r1-r0 (mod u1*g) (u0*g = m0, u1*g = m1)
// -> x = (r1 - r0) / g * inv(u0) (mod u1)
// im = inv(u0) (mod u1) (0 <= im < u1)
long long g, im;
std::tie(g, im) = internal::inv_gcd(m0, m1);
long long u1 = (m1 / g);
// |r1 - r0| < (m0 + m1) <= lcm(m0, m1)
if ((r1 - r0) % g) return {0, 0};
// u1 * u1 <= m1 * m1 / g / g <= m0 * m1 / g = lcm(m0, m1)
long long x = (r1 - r0) / g % u1 * im % u1;
// |r0| + |m0 * x|
// < m0 + m0 * (u1 - 1)
// = m0 + m0 * m1 / g - m0
// = lcm(m0, m1)
r0 += x * m0;
m0 *= u1; // -> lcm(m0, m1)
if (r0 < 0) r0 += m0;
}
return {r0, m0};
}
inline long long floor_sum(long long n, long long m, long long a, long long b) {
assert(0 <= n && n < (1LL << 32));
assert(1 <= m && m < (1LL << 32));
unsigned long long ans = 0;
if (a < 0) {
unsigned long long a2 = internal::safe_mod(a, m);
ans -= 1ULL * n * (n - 1) / 2 * ((a2 - a) / m);
a = a2;
}
if (b < 0) {
unsigned long long b2 = internal::safe_mod(b, m);
ans -= 1ULL * n * ((b2 - b) / m);
b = b2;
}
return ans + internal::floor_sum_unsigned(n, m, a, b);
}
} // namespace e6nlaq
#line 2 "include/e6nlaq/math/integer.hpp"
#define E6NLAQ_MATH_INTEGER_HPP
#include <bit>
#line 7 "include/e6nlaq/math/integer.hpp"
#include <concepts>
#include <cstdlib>
#include <limits>
#include <stdexcept>
namespace e6nlaq {
/**
* @brief 符号なし整数の桁数を計算します
* @tparam T 符号なし整数型
* @param n 桁数を計算する整数
* @return int 10進数表記での桁数
* @note 計算量: O(1)
* @see https://x.com/ngtkana/status/1980504937290428680
*/
template <std::unsigned_integral T>
int digits(T n) {
using UnsignedT = std::make_unsigned_t<T>;
UnsignedT x;
if (n < 0)
x = static_cast<UnsignedT>(-n);
else
x = n;
x |= 1;
if constexpr (sizeof(UnsignedT) <= 4) { // 32bit or less
static const int lower_bound_table[] = {9, 9, 9, 8, 8, 8, 7, 7, 7, 6, 6, 6, 6, 5, 5, 5, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 0, 0, 0};
static const unsigned int pow[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
int lower_bound = lower_bound_table[std::countl_zero(static_cast<unsigned int>(x))];
return lower_bound + (pow[lower_bound] <= x);
} else { // 64bit
static const int lower_bound_table[] = {
19, 18, 18, 18, 18, 17, 17, 17, 16, 16, 16, 16, 15, 15, 15, 14, 14, 14, 13, 13, 13, 13,
12, 12, 12, 11, 11, 11, 11, 10, 10, 10, 9, 9, 9, 9, 8, 8, 8, 7, 7, 7, 7, 6, 6, 6,
5, 5, 5, 5, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 0};
static const unsigned long long pow[] = {
1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000,
10000000000ULL, 100000000000ULL, 1000000000000ULL, 10000000000000ULL,
100000000000000ULL, 1000000000000000ULL, 10000000000000000ULL,
100000000000000000ULL, 1000000000000000000ULL, 10000000000000000000ULL};
int lower_bound = lower_bound_table[std::countl_zero(x)];
return lower_bound + (pow[lower_bound] <= x);
}
}
/**
* @brief 符号付き整数の桁数を計算します
* @tparam T 符号付き整数型
* @param n 桁数を計算する整数
* @return int 10進数表記での桁数（符号は除く）
* @note 計算量: O(1)
*/
template <std::signed_integral T>
int digits(T n) {
return digits(static_cast<std::make_unsigned_t<T>>(n < 0 ? -n : n));
}
/**
* @brief 非負整数の平方根の整数部を計算します（切り捨て）
* @tparam T 整数型
* @param n 非負整数（n >= 0）
* @return T floor(√n) の値
* @note 計算量: O(log log N) / 実質O(1)
* @note ニュートン法を使用して実装されています
* @throw std::invalid_argument nが負の場合にスローされます
*/
template <std::integral T>
T isqrt(T n) {
if (n < 0) {
throw std::invalid_argument("isqrt: n must be non-negative");
}
if (n == 0) {
return 0;
}
using UnsignedT = std::make_unsigned_t<T>;
UnsignedT n_unsigned = static_cast<UnsignedT>(n);
int n_bits = std::bit_width(n_unsigned);
T x;
int shift = (n_bits + 1) / 2;
constexpr int t_digits = std::numeric_limits<T>::digits;
if (shift >= t_digits) {
x = static_cast<T>(1) << (t_digits - 1);
} else {
x = static_cast<T>(1) << shift;
}
T y = (x + n / x) / 2;
while (y < x) {
x = y;
y = (x + n / x) / 2;
}
return x;
}
/**
* @brief 与えられた整数が平方数かどうかを判定します
* @tparam T 整数型
* @param N 判定する整数
* @return bool Nが平方数の場合はtrue、そうでない場合はfalse
* @note 計算量: isqrt(N) に依存
* @note 例外を投げないことが保証されています
*/
template <std::integral T>
inline bool is_square(const T N) noexcept {
T r = isqrt(N); // 切り捨てした平方根
return (r * r) == N;
}
/**
* @brief 切り上げ(無限大方向)除算を行います
* @tparam T 整数型
* @param a 被除数
* @param b 0でない除数 (b != 0)
* @return T ceil(a / b) の値（正の無限大方向に丸め）
* @throw std::invalid_argument bが0の場合
* @note 計算量: O(1)
* @note a や b が負の場合も正の無限大方向に丸めます
*/
template <std::integral T>
inline constexpr T div_ceil(T a, T b) {
if (b == 0) {
throw std::invalid_argument("div_ceil: division by zero");
}
T res = a / b;
T rem = a % b;
// 剰余があり、かつaとbが同符号（結果が正）の場合に切り上げる
if (rem != 0 && (a > 0 == b > 0)) {
res++;
}
return res;
}
/**
* @brief 数学的な意味での剰余を計算します（負の数にも対応）
* @tparam T 整数型
* @param x 被除数
* @param m 0でない除数 (m != 0)
* @return T x mod m の値（0以上m未満）
* @note 計算量: O(1)
* @note 常に0以上m未満の値を返します
* @see https://qiita.com/happyisland44/items/8e4feb6805eecee29f83
*/
template <std::integral T>
inline constexpr T mmod(T x, T m) {
T M = m;
if constexpr (std::is_signed_v<T>) {
if (m < 0) {
if (m == std::numeric_limits<T>::min()) {
throw std::domain_error("mmod: m cannot be the minimum value of its type");
}
M = -m;
}
}
T r = x % M;
return r < 0 ? r + M : r;
}
/**
* @brief 非負整数の階乗を計算します
* @param n 非負整数 (n >= 0)
* @return long long n! の値
* @note 計算量: O(n)
* @note nが0の場合は1を返します
* @warning nが大きいとオーバーフローする可能性があります（20! = 2,432,902,008,176,640,000）
*/
inline constexpr unsigned long long fact(const unsigned long long n) {
unsigned long long res = 1;
for (unsigned long long i = 2; i <= n; i++) {
res *= i;
}
return res;
}
/**
* @brief 整数のべき乗を計算します (x^n)
* @param x 底
* @param n 指数
* @return unsigned long long x^n の値
* @note 計算量: O(log n)
* @note 繰り返し二乗法を使用して実装されています
* @note 0^0=1です
* @warning 結果がオーバーフローする可能性があります
*/
inline unsigned long long pow_ll(unsigned long long x, unsigned long long n) noexcept {
unsigned long long ret = 1ULL;
while (n > 0) {
if (n & 1)
ret *= x;
x *= x;
n >>= 1;
}
return ret;
}
/**
* @brief 1からnまでの総和を計算します
* @param n 非負整数
* @return unsigned long long 1 + 2 + ... + n の値
* @note 計算量: O(1)
* @note 公式: n(n+1)/2 を使用して実装されています
* @warning nが大きいとオーバーフローする可能性があります
*/
inline unsigned long long sum_to_n(const unsigned long long n) noexcept {
if (n % 2 == 0) {
return (n / 2ULL) * (n + 1ULL);
} else {
return n * ((n + 1ULL) / 2ULL);
}
}
} // namespace e6nlaq
#line 3 "include/e6nlaq/math.hpp"
include/e6nlaq/math.hpp