#pragma once
#include "../../math/qpow/basic/lib.hpp"
namespace tifa_libs {
// consider line s: y = (p * x + r) / q, 0 < x <= l
// result will add a when s cross with horizontal line
// result will add b when s cross with vertical line
template <class TIFA>
CEXP TIFA exeuclid(i64 p, i64 q, i64 r, i64 l, TIFA CR a, TIFA CR b) NE {
#pragma GCC diagnostic ignored "-Wfloat-conversion"
auto div = [](i64 a, i64 b, i64 c, i64 d) NE -> i64 { return (1.l * a * b + c) / d; };
#pragma GCC diagnostic warning "-Wfloat-conversion"
auto f = [&](auto&& f, i64 p, i64 q, i64 r, i64 l, cT_(TIFA) a, cT_(TIFA) b) NE -> TIFA {
if (!l) return {};
if (p >= q) return f(f, p % q, q, r, l, a, qpow(a, u64(p / q), TIFA{}) * b);
ci64 m = div(l, p, r, q);
if (!m) return qpow(b, (u64)l, TIFA{});
ci64 cnt = l - div(q, m, -r - 1, p);
return qpow(b, u64((q - r - 1) / p), TIFA{}) * a * f(f, q, p, (q - r - 1) % p, m - 1, b, a) * qpow(b, (u64)cnt, TIFA{});
};
return qpow(a, u64(r / q), TIFA{}) * f(f, p, q, r % q, l, a, b);
}
} // namespace tifa_libs
#line 2 "src/math/exeuclid/lib.hpp"
#line 2 "src/math/qpow/basic/lib.hpp"
#line 2 "src/util/alias/num/lib.hpp"
#line 2 "src/util/util/lib.hpp"
// https://github.com/Tiphereth-A/CP-lib
#include <bits/extc++.h>
// clang-format off
namespace tifa_libs {
#define CEXP constexpr
#define CEXPE constexpr explicit
#define CR const&
#define CP const*
#define PC *const
#define CPC const*const
#define TPN typename
#define NE noexcept
#define CNE const noexcept
#define ND [[nodiscard]]
#define cT_(...) std::conditional_t<sizeof(__VA_ARGS__) <= sizeof(size_t) * 2, __VA_ARGS__, __VA_ARGS__ CR>
// NOLINTNEXTLINE(misc-const-correctness)
#define flt_(T, i, l, r, ...) for (T i = (l), i##e = (r)__VA_OPT__(, ) __VA_ARGS__; i < i##e; ++i)
#define retif_(cond, if_true, ...) if cond return if_true __VA_OPT__(; else return __VA_ARGS__)
#ifdef ONLINE_JUDGE
#undef assert
#define assert(x) 42
#endif
using namespace std::ranges;
using namespace std::literals;
template <class T>
CEXP T abs(T x) NE { retif_((x < 0), -x, x); }
} // namespace tifa_libs
// clang-format on
#line 4 "src/util/alias/num/lib.hpp"
// clang-format off
namespace tifa_libs {
#define mk0_(w, t) using w = t; using c##w = const t
#define mk_(w, t) mk0_(w, t); CEXP w operator""_##w(unsigned long long x) NE { return (w)x; }
mk_(i8, int8_t) mk_(u8, uint8_t) mk_(i16, int16_t) mk_(u16, uint16_t) mk_(i32, int32_t) mk_(u32, uint32_t) mk_(i64, int64_t) mk_(u64, uint64_t) mk_(isz, ssize_t) mk_(usz, size_t) mk_(chr, char) mk_(schr, signed char) mk_(uchr, unsigned char) mk_(sint, signed) mk_(uint, unsigned);
mk0_(i128, __int128_t); mk0_(u128, __uint128_t); mk0_(f32, float); mk0_(f64, double); mk0_(f128, long double);
#undef mk0_
#undef mk_
} // namespace tifa_libs
// clang-format on
#line 4 "src/math/qpow/basic/lib.hpp"
namespace tifa_libs {
template <class T>
CEXP T qpow(T a, u64 b, cT_(T) init_v = T{1}) NE {
T res = init_v;
for (; b; b >>= 1, a = a * a) {
while (!(b & 1)) b >>= 1, a = a * a;
res = res * a;
}
return res;
}
} // namespace tifa_libs
#line 4 "src/math/exeuclid/lib.hpp"
namespace tifa_libs {
// consider line s: y = (p * x + r) / q, 0 < x <= l
// result will add a when s cross with horizontal line
// result will add b when s cross with vertical line
template <class TIFA>
CEXP TIFA exeuclid(i64 p, i64 q, i64 r, i64 l, TIFA CR a, TIFA CR b) NE {
#pragma GCC diagnostic ignored "-Wfloat-conversion"
auto div = [](i64 a, i64 b, i64 c, i64 d) NE -> i64 { return (1.l * a * b + c) / d; };
#pragma GCC diagnostic warning "-Wfloat-conversion"
auto f = [&](auto&& f, i64 p, i64 q, i64 r, i64 l, cT_(TIFA) a, cT_(TIFA) b) NE -> TIFA {
if (!l) return {};
if (p >= q) return f(f, p % q, q, r, l, a, qpow(a, u64(p / q), TIFA{}) * b);
ci64 m = div(l, p, r, q);
if (!m) return qpow(b, (u64)l, TIFA{});
ci64 cnt = l - div(q, m, -r - 1, p);
return qpow(b, u64((q - r - 1) / p), TIFA{}) * a * f(f, q, p, (q - r - 1) % p, m - 1, b, a) * qpow(b, (u64)cnt, TIFA{});
};
return qpow(a, u64(r / q), TIFA{}) * f(f, p, q, r % q, l, a, b);
}
} // namespace tifa_libs
src/math/exeuclid/lib.hpp