1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
| #include <bits/stdc++.h>
#define fi first
#define se second
#define Mp make_pair
#define pb push_back
#define SZ(a) (int(a.size()))
typedef long long ll;
typedef double db;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
#define debug(...) fprintf(stderr, __VA_ARGS__)
std::mt19937_64 gen(std::chrono::system_clock::now().time_since_epoch().count());
ll get(ll l, ll r) { std::uniform_int_distribution<ll> dist(l, r); return dist(gen); }
typedef unsigned long long ull;
int rem[256][256];
ull nimProd(ull x, ull y, int p = 32) {
if (x <= 1 || y <= 1) return x * y;
if (p < 8 && rem[x][y]) return rem[x][y];
ull a = x >> p, b = ((1ull << p) - 1) & x, c = y >> p, d = ((1ull << p) - 1) & y;
ull bd = nimProd(b, d, p >> 1), ac = nimProd(nimProd(a, c, p >> 1), 1ull << p >> 1, p >> 1), ans;
ans = ((nimProd(a ^ b, c ^ d, p >> 1) ^ bd) << p) ^ ac ^ bd;
if (p < 8) rem[x][y] = rem[y][x] = ans;
return ans;
}
template<class T>
T power(T a, ull b) {
T res = 1;
while(b) {
if(b & 1) res *= a;
a *= a, b >>= 1;
}
return res;
}
struct nimber {
ull z;
nimber(ull _z = 0) : z(_z) {}
ull val() { return z; }
friend bool operator==(nimber a, nimber b) { return a.z == b.z; }
friend nimber operator+(nimber a, nimber b) { return nimber(a.z ^ b.z); }
friend nimber operator-(nimber a, nimber b) { return nimber(a.z ^ b.z); }
friend nimber operator*(nimber a, nimber b) { return nimber(nimProd(a.z, b.z)); }
nimber &operator+=(nimber b) { return (*this) = (*this) + b; }
nimber &operator-=(nimber b) { return (*this) = (*this) + b; }
nimber &operator*=(nimber b) { return (*this) = (*this) * b; }
nimber inv() const { return power(*this, -2ull); }
nimber sqrt(nimber b) const { return power(b.z, 1ull << 63); }
friend nimber operator/(nimber a, nimber b) { return nimber(a.z * b.inv()); }
nimber &operator/=(nimber b) { return (*this) = (*this) / b; }
friend std::istream &operator>>(std::istream &is, nimber &a) {
ull v; is >> v; a = nimber(v); return is;
}
friend std::ostream &operator<<(std::ostream &os, nimber &a) {
return os << a.val();
}
};
struct poly {
std::vector<nimber> a;
poly(int size, int val = 0) : a(size, val) {}
poly(const std::vector<nimber> &ve) : a(ve) {}
int size() { return SZ(a); }
void resize(int n) { a.resize(n); }
friend poly operator*(poly a, poly b) {
poly c(SZ(a) + SZ(b));
for(int i = 0; i < SZ(a); i++)
for(int j = 0; j < SZ(b); j++)
c.a[i + j] += a.a[i] * b.a[j];
return c;
}
friend poly operator%(poly a, poly b) {
int id = SZ(b) - 1;
for(int i = SZ(a) - 1; i >= id; i--) {
auto d = a.a[i] / b.a[id];
for(int j = 0; j <= id; j++)
a.a[i - j] -= d * b.a[id - j];
}
while(a.a.back() == nimber(0)) a.a.pop_back();
return a;
}
friend poly operator-(poly a, poly b) {
assert(SZ(b) == 1);
a.a[0] -= b.a[0];
return a;
}
};
poly qpow(poly a, ull b, poly mod) {
poly res = poly({nimber(1)});
while(b) {
if(b & 1) res = res * a % mod;
a = a * a % mod, b >>= 1;
}
return res;
}
poly gcd(poly a, poly b) { return SZ(b) ? gcd(b, a % b) : a; }
int q, n; nimber a, b;
signed main() {
std::ios::sync_with_stdio(false);
std::cin >> n;
for(int i = 1; i <= n; i++) {
nimber x; std::cin >> x;
a += x, b += x * x * x;
}
if(q == 2) {
auto c = b / a;
auto d = c - a * a;
auto px = poly({d, a, 1});
nimber x, y;
while(1) {
auto r = gen();
auto pow = qpow(poly({r, nimber(1)}), -1ull / 3, px) - poly({nimber(1)});
auto g = gcd(pow, px);
if(SZ(g) == 2) {
x = g.a[0] / g.a[1];
break;
}
}
y = a - x;
a = x, b = y;
}
std::cout << a << ' ' << b << '\n';
std::cerr << (db)clock()/CLOCKS_PER_SEC << "s\n";
return 0;
}
|