// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/nim_product_64
#include "../../../src/math/nim_prod/lib.hpp"
using namespace tifa_libs;
int main() {
std::cin.tie(nullptr)->std::ios::sync_with_stdio(false);
u32 t;
std::cin >> t;
for (u64 i = 0, a, b; i < t; ++i) {
std::cin >> a >> b;
std::cout << nimprod64(a, b) << '\n';
}
return 0;
}
#line 1 "test/cpv/library-checker-number_theory/nim_product_64.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/nim_product_64
#line 2 "src/math/nim_prod/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/nim_prod/lib.hpp"
namespace tifa_libs {
namespace nim_prod_impl_ {
struct calc8 {
// NOLINTNEXTLINE(modernize-avoid-c-arrays)
u16 dp[1 << 8][1 << 8]{};
CEXPE calc8() NE {
dp[0][0] = dp[0][1] = dp[1][0] = 0, dp[1][1] = 1;
flt_ (u32, e, 1, 4) {
cu32 p = 1 << e, q = p >> 1;
cu16 ep = u16(1u << p), eq = u16(1u << q);
flt_ (u16, i, 0, ep)
flt_ (u16, j, i, ep) {
if (i < eq && j < eq) continue;
if (std::min(i, j) <= 1u) {
dp[i][j] = dp[j][i] = i * j;
continue;
}
cu16 iu = u16(i >> q), il = u16(i & (eq - 1)), ju = u16(j >> q), jl = u16(j & (eq - 1));
cu16 u = dp[iu][ju], l = dp[il][jl], ul = dp[iu ^ il][ju ^ jl], uq = dp[u][eq >> 1];
dp[i][j] = u16((ul ^ l) << q) ^ uq ^ l, dp[j][i] = dp[i][j];
}
}
}
} CEXP c8;
struct calc16 {
static CEXP u16 proot = 10279;
static CEXP u32 ppoly = 92191, order = 65535;
// NOLINTNEXTLINE(modernize-avoid-c-arrays)
u16 base[16]{}, exp[(1 << 18) + 100]{};
// NOLINTNEXTLINE(modernize-avoid-c-arrays)
u32 log[1 << 16]{};
private:
CEXP u16 d(u32 x) NE {
auto _ = x < 32768u ? 0 : ppoly;
return u16((x << 1) ^ _);
}
CEXP u16 naive(u16 i, u16 j) NE {
if (min(i, j) <= 1u) return i * j;
cu16 q = 8, eq = 1u << 8;
cu16 iu = u16(i >> q), il = u16(i & (eq - 1)), ju = u16(j >> q), jl = u16(j & (eq - 1));
cu16 u = c8.dp[iu][ju], l = c8.dp[il][jl], ul = c8.dp[iu ^ il][ju ^ jl], uq = c8.dp[u][eq >> 1];
return u16((ul ^ l) << q) ^ uq ^ l;
}
public:
CEXPE calc16() NE {
base[0] = 1;
flt_ (u32, i, 1, 16) base[i] = naive(base[i - 1], proot);
exp[0] = 1;
flt_ (u32, i, 1, order) exp[i] = d(exp[i - 1]);
u16* pre = exp + order + 1;
pre[0] = 0;
flt_ (u32, b, 0, 16) {
cu32 is = 1 << b;
flt_ (u32, i, is, is * 2) pre[i] = pre[i - is] ^ base[b];
}
flt_ (u32, i, 0, order) exp[i] = pre[exp[i]], log[exp[i]] = i;
cu32 ie_ = 2 * order + 30;
flt_ (u32, i, order, ie_) exp[i] = exp[i - order];
for (u32 i = ie_; i < sizeof(exp) / sizeof(u16); ++i) exp[i] = 0;
log[0] = ie_ + 1;
}
ND CEXP u16 prod(u16 i, u16 j) CNE { return exp[log[i] + log[j]]; }
// exp[3] = 2^{15} = 32768
ND CEXP u16 Hprod(u16 i, u16 j) CNE { return exp[log[i] + log[j] + 3]; }
ND CEXP u16 H(u16 i) CNE { return exp[log[i] + 3]; }
ND CEXP u16 H2(u16 i) CNE { return exp[log[i] + 6]; }
} CEXP c16;
CEXP u16 nimprod16(u16 i, u16 j) NE { return c16.prod(i, j); }
CEXP u32 nimprod32(u32 i, u32 j) NE {
cu16 iu = u16(i >> 16), il = u16(i & 65535), ju = u16(j >> 16), jl = u16(j & 65535);
cu16 l = c16.prod(il, jl), ul = c16.prod(iu ^ il, ju ^ jl), uq = c16.Hprod(iu, ju);
return (u32(ul ^ l) << 16) ^ uq ^ l;
}
// (+ : xor, x : nim product, * : integer product)
// i x j
// = (iu x ju + il x ju + iu x ji) * 2^{16}
// + (iu x ju x 2^{15}) + il x jl
// (assign ju = 2^{15}, jl = 0)
// = ((iu + il) x 2^{15}) * 2^{16} + (iu x 2^{15} x 2^{15})
CEXP u32 H(u32 i) NE {
cu16 iu = u16(i >> 16), il = u16(i & 65535);
return (u32(c16.H(iu ^ il)) << 16) ^ c16.H2(iu);
}
CEXP u64 nimprod64(u64 i, u64 j) NE {
cu32 iu = u32(i >> 32), il = u32(i & u32(-1)), ju = u32(j >> 32), jl = u32(j & u32(-1));
cu32 l = nimprod32(il, jl), ul = nimprod32(iu ^ il, ju ^ jl), uq = H(nimprod32(iu, ju));
return (u64(ul ^ l) << 32) ^ uq ^ l;
}
} // namespace nim_prod_impl_
using nim_prod_impl_::nimprod16, nim_prod_impl_::nimprod32, nim_prod_impl_::nimprod64;
} // namespace tifa_libs
#line 3 "test/cpv/library-checker-number_theory/nim_product_64.cpp"
using namespace tifa_libs;
int main() {
std::cin.tie(nullptr)->std::ios::sync_with_stdio(false);
u32 t;
std::cin >> t;
for (u64 i = 0, a, b; i < t; ++i) {
std::cin >> a >> b;
std::cout << nimprod64(a, b) << '\n';
}
return 0;
}
test/cpv/library-checker-number_theory/nim_product_64.cpp