Submit Info #4711

Problem Lang User Status Time Memory
Nim Product ($\mathbb{F}_{2^{64}}$) cpp Min AC 511 ms 19.96 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.68 MiB
large_00 AC 498 ms 19.96 MiB
large_few_00 AC 55 ms 2.42 MiB
power_of_two_00 AC 3 ms 0.67 MiB
random_00 AC 509 ms 19.96 MiB
random_01 AC 511 ms 19.96 MiB
random_few_00 AC 57 ms 2.44 MiB
random_few_01 AC 58 ms 2.50 MiB
small_00 AC 304 ms 5.92 MiB
small_few_00 AC 35 ms 0.92 MiB

#include <cstdio> using u64 = unsigned long long; constexpr u64 masks[] = { 0x5555555555555555, 0x3333333333333333, 0x0f0f0f0f0f0f0f0f, 0x00ff00ff00ff00ff, 0x0000ffff0000ffff, 0x00000000ffffffff }; template <int i> constexpr u64 nim_mul(u64 a, u64 b) { u64 s = nim_mul<i - 1>(a, b); u64 m = masks[i - 1]; int k = 1 << (i - 1); u64 t = nim_mul<i - 1>(((a^(a>>k))&m) | (s&~m), ((b^(b>>k))&m) | (m&(~m>>1))<<k); return ((s^t)&m)<<k | ((s^(t>>k))&m); } template <> constexpr u64 nim_mul<0>(u64 a, u64 b) { return a & b; } constexpr u64 nim_mul(u64 a, u64 b) { return nim_mul<6>(a, b); } template <int i> constexpr u64 nim_half(u64 a) { u64 h = nim_half<i - 1>(a); u64 m = masks[i - 1]; int k = 1 << (i - 1); return ((h ^ (h << k)) & ~m) | nim_half<i - 1>((h >> k) & m); } template <> constexpr u64 nim_half<0>(u64 a) { return a; } constexpr u64 nim_half(u64 a) { return nim_half<6>(a); } template <int i> constexpr u64 nim_inv(u64 a) { u64 m = masks[i - 1]; int k = 1 << (i - 1); u64 h = (a >> k) & m; if (!h) return nim_inv<i - 1>(a); u64 r = a ^ h; u64 s = nim_mul<i - 1>(a, r); u64 t = nim_half<i - 1>((s >> k) & m); u64 v = nim_inv<i - 1>((s & m) ^ t); return nim_mul<i - 1>(v << k | v, r); } template <> constexpr u64 nim_inv<0>(u64 a) { return a; } constexpr u64 nim_inv(u64 a) { return nim_inv<6>(a); } template <int i> constexpr u64 nim_sqrt(u64 a) { u64 m = masks[i - 1]; int k = 1 << (i - 1); return nim_sqrt<i - 1>(a ^ nim_half<i - 1>((a >> k) & m)); } template <> constexpr u64 nim_sqrt<0>(u64 a) { return a; } constexpr u64 nim_sqrt(u64 a) { return nim_sqrt<6>(a); } template <int i> constexpr u64 nim_square(u64 a) { u64 m = masks[i - 1]; int k = 1 << (i - 1); u64 s = nim_square<i - 1>(a); return s ^ nim_half<i - 1>((s >> k) & m); } template <> constexpr u64 nim_square<0>(u64 a) { return a; } constexpr u64 nim_square(u64 a) { return nim_square<6>(a); } int main() { int T; scanf("%d", &T); for (int i = 0; i < T; ++i) { u64 a, b; scanf("%llu %llu", &a, &b); printf("%llu\n", nim_mul(a, b)); } return 0; }