This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub tko919/library
#define PROBLEM "https://judge.yosupo.jp/problem/nim_product_64" #include "Template/template.hpp" #include "Math/nimber.hpp" int main(){ int t; cin>>t; while(t--){ Nimber a,b; cin>>a>>b; cout<<a*b<<'\n'; } return 0; }
#line 1 "Verify/LC_nim_product_64.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/nim_product_64" #line 1 "Template/template.hpp" #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++) #define rrep(i, a, b) for (int i = (int)(b-1); i >= (int)(a); i--) #define ALL(v) (v).begin(), (v).end() #define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end()) #define SZ(v) (int)v.size() #define MIN(v) *min_element(ALL(v)) #define MAX(v) *max_element(ALL(v)) #define LB(v, x) int(lower_bound(ALL(v), (x)) - (v).begin()) #define UB(v, x) int(upper_bound(ALL(v), (x)) - (v).begin()) using uint = unsigned int; using ll = long long int; using ull = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; template <typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; } template <typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return 1; } return 0; } template <typename T, typename U> T ceil(T x, U y) { assert(y != 0); if (y < 0) x = -x, y = -y; return (x > 0 ? (x + y - 1) / y : x / y); } template <typename T, typename U> T floor(T x, U y) { assert(y != 0); if (y < 0) x = -x, y = -y; return (x > 0 ? x / y : (x - y + 1) / y); } template <typename T> int popcnt(T x) { return __builtin_popcountll(x); } template <typename T> int topbit(T x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } template <typename T> int lowbit(T x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } #ifdef LOCAL #define show(...) _show(0, #__VA_ARGS__, __VA_ARGS__) #else #define show(...) true #endif template <typename T> void _show(int i, T name) { cerr << '\n'; } template <typename T1, typename T2, typename... T3> void _show(int i, const T1 &a, const T2 &b, const T3 &...c) { for (; a[i] != ',' && a[i] != '\0'; i++) cerr << a[i]; cerr << ":" << b << " "; _show(i + 1, a, c...); } template <class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p) { os << "P(" << p.first << ", " << p.second << ")"; return os; } template <typename T, template <class> class C> ostream &operator<<(ostream &os, const C<T> &v) { os << "["; for (auto d : v) os << d << ", "; os << "]"; return os; } #line 2 "Math/nimber.hpp" using ull=unsigned long long; struct NimberManager{ ull memo[256][256]; NimberManager(){ rep(i,0,256)rep(j,0,256)memo[i][j]=256; memo[0][0]=memo[0][1]=memo[1][0]=0; memo[1][1]=1; rep(i,0,256)rep(j,0,256)memo[i][j]=mul(i,j,8); } ull mul(ull x,ull y,int k=64){ if(k<=8&&memo[x][y]<256)return memo[x][y]; k>>=1; ull a=x>>k,b=x^(a<<k),c=y>>k,d=y^(c<<k); ull ac=mul(a,c,k),bd=mul(b,d,k),abcd=mul(a^b,c^d,k); return mul(ac,1ull<<(k-1),k)^(abcd^bd)<<k^bd; } }; NimberManager Nim; struct Nimber{ ull v; Nimber(ull _v=0):v(_v){} Nimber& operator+=(const Nimber& x){v^=x.v; return *this;} Nimber& operator-=(const Nimber& x){v^=x.v; return *this;} Nimber& operator*=(const Nimber& x){v=Nim.mul(v,x.v); return *this;} Nimber operator+(const Nimber& x)const{return Nimber(*this)+=x;} Nimber operator-(const Nimber& x)const{return Nimber(*this)-=x;} Nimber operator*(const Nimber& x)const{return Nimber(*this)*=x;} bool operator==(const Nimber& x)const{return v==x.v;} bool operator!=(const Nimber& x)const{return v!=x.v;} friend istream& operator>>(istream& is,Nimber& x){return is>>x.v;} friend ostream& operator<<(ostream& os,const Nimber& x){return os<<x.v;} }; /** * @brief Nimber */ #line 5 "Verify/LC_nim_product_64.test.cpp" int main(){ int t; cin>>t; while(t--){ Nimber a,b; cin>>a>>b; cout<<a*b<<'\n'; } return 0; }