Submit Info #4589

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

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.71 MiB
large_00 AC 543 ms 20.05 MiB
large_few_00 AC 61 ms 2.46 MiB
power_of_two_00 AC 5 ms 0.72 MiB
random_00 AC 547 ms 19.96 MiB
random_01 AC 548 ms 19.96 MiB
random_few_00 AC 60 ms 2.47 MiB
random_few_01 AC 58 ms 2.42 MiB
small_00 AC 341 ms 5.96 MiB
small_few_00 AC 39 ms 0.92 MiB

#include <cstdio> using u64 = unsigned long long; const u64 masks[] = { 0x5555555555555555, 0x3333333333333333, 0x0f0f0f0f0f0f0f0f, 0x00ff00ff00ff00ff, 0x0000ffff0000ffff, 0x00000000ffffffff }; u64 nimber_mul(u64 a, u64 b, int i=6) { if (i == 1) { u64 s = a & b; u64 m = masks[0]; u64 t = (a^(a>>1)) & (b^(b>>1)); return ((s^t)&m)<<1 | ((s^(s>>1))&m); } else { u64 s = nimber_mul(a, b, --i); u64 m = masks[i]; int k = 1 << i; u64 t = nimber_mul(((a^(a>>k))&m) | (s&~m), ((b^(b>>k))&m) | (m&(~m>>1))<<k, i); return ((s^t)&m)<<k | ((s^(t>>k))&m); } } u64 nimber_inv(u64 a, int i=6) { if (i == 1) return a ^ (a >> 1); u64 m = masks[--i]; int k = 1 << i; if (!(a >> k)) return nimber_inv(a, i); u64 r = a ^ (a >> k); u64 s = nimber_mul(a, r, i); u64 t = nimber_mul(s >> k, m & (~m >> 1), i); u64 v = nimber_inv((s & m) ^ t, i); return nimber_mul(v << k | v, r, i); } 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", nimber_mul(a, b)); } return 0; }