#include <bits/stdc++.h>
#ifndef LOCAL
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
using namespace std;
#define int long long
#define tmp template <class T>
#define vec vector
#define i32 int32_t
#define i64 int64_t
using pii = pair<int, int>;
// #define F(...) [&](auto&& x) { __VA_ARGS__; }
// #define G(...) [&](auto&& a, auto&& b) { __VA_ARGS__; }
#define len(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rev(x) rbegin(x), rend(x)
#define X first
#define Y second
int collisions(vec<int> x);
#ifdef LOCAL
int n;
int calls;
int collisions(vec<int> a) {
calls += a.size();
int ans = 0;
map<int, int> f;
for (int x: a) {
ans += f[x % n]++;
}
return ans;
}
#endif
typedef unsigned long long ull;
typedef __uint128_t u128;
ull fast_gcd(ull a, ull b) {
if (!a || !b) return a | b;
int shift = __builtin_ctzll(a | b);
a >>= __builtin_ctzll(a);
do {
b >>= __builtin_ctzll(b);
if (a > b) std::swap(a, b);
b -= a;
} while (b);
return a << shift;
}
struct Montgomery {
ull n, nr;
constexpr Montgomery(ull n) : n(n), nr(1) {
for (int i = 0; i < 6; i++) { nr *= 2ULL - n * nr; }
}
ull reduce(u128 x) const {
ull q = ull(x) * nr;
ull m = ((u128)q * n) >> 64;
ull y = (x >> 64) + n - m;
return y >= n ? y - n : y;
}
ull multiply(ull x, ull y) const { return reduce((u128)x * y); }
ull transform(ull x) const { return (ull)(((u128)x << 64) % n); }
ull pow(ull base, ull exp) const {
ull res = transform(1);
for (; exp; exp >>= 1, base = multiply(base, base)) {
if (exp & 1) res = multiply(res, base);
}
return res;
}
};
ull pollard(ull n) {
if (n % 2 == 0) return 2;
Montgomery space(n);
ull one = space.transform(1);
auto f = [&](ull x) {
ull res = space.multiply(x, x) + one;
return res >= n ? res - n : res;
};
ull x = 0, y = 0, t = 30, prd = space.transform(2), i = 1, q;
while (t++ % 40 || fast_gcd(space.reduce(prd), n) == 1) {
if (x == y) x = space.transform(++i), y = f(x);
ull diff = x > y ? x - y : y - x;
if ((q = space.multiply(prd, diff))) prd = q;
x = f(x), y = f(f(y));
}
return fast_gcd(space.reduce(prd), n);
}
bool isPrime(ull n) {
if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
Montgomery space(n);
ull A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
ull s = __builtin_ctzll(n - 1), d = n >> s;
ull one = space.transform(1), minus_one = n - one;
for (ull a : A) {
if (a % n == 0) continue;
ull p = space.pow(space.transform(a % n), d);
ull i = s;
while (p != one && p != minus_one && i--) p = space.multiply(p, p);
if (p != minus_one && i != s) return 0;
}
return 1;
}
vec<ull> factor(ull n) {
if (n == 1) return {};
if (isPrime(n)) return {n};
ull x = pollard(n);
auto l = factor(x), r = factor(n / x);
l.insert(l.end(), all(r));
return l;
}
ull primeFactor(ull n) {
if (n < 2) return 0;
if (isPrime(n)) return n;
ull d = pollard(n);
return primeFactor(d);
}
vec<ull> listDivs(ull n) {
if (!n) return {};
vec<ull> pr = factor(n), divs = {1};
sort(all(pr));
for (int i = 0, j; i < pr.size(); i = j) {
for (j = i; j < pr.size() && pr[j] == pr[i]; j++);
int count = j - i, sz = divs.size();
ull p_pow = 1;
for (int k = 0; k < count; k++) {
p_pow *= pr[i];
for (int m = 0; m < sz; m++) divs.push_back(divs[m] * p_pow);
}
}
sort(all(divs));
return divs;
}
pair<int, int> solve(vec<int> objects) {
vec<int> s1, s2;
auto get_split = [&](auto& self, vec<int> s) -> void {
int mid = s.size() / 2;
vec<int> L(s.begin(), s.begin() + mid);
vec<int> R(s.begin() + mid, s.end());
if (collisions(L) >= 1) {
self(self, L);
} else if (collisions(R) >= 1) {
self(self, R);
} else {
s1 = L;
s2 = R;
}
};
get_split(get_split, objects);
while (s1.size() > 1 || s2.size() > 1) {
if (s1.size() > 1) {
int mid = s1.size() / 2;
vec<int> L1(s1.begin(), s1.begin() + mid);
vec<int> R1(s1.begin() + mid, s1.end());
vec<int> query = L1;
query.insert(query.end(), all(s2));
if (collisions(query) >= 1) s1 = L1;
else s1 = R1;
}
if (s2.size() > 1) {
int mid = s2.size() / 2;
vec<int> L2(s2.begin(), s2.begin() + mid);
vec<int> R2(s2.begin() + mid, s2.end());
vec<int> query = L2;
query.insert(query.end(), all(s1));
if (collisions(query) >= 1) s2 = L2;
else s2 = R2;
}
}
return {s1[0], s2[0]};
}
signed hack_old() {
int mul = 1;
vec<int> s;
for (int i = 2; i <= 1'000'000; i++) {
mul *= i;
s.push_back(i);
if (mul > (int)1e9) {
if (collisions({mul + 1, 1}) == 1) {
// now the N is some factor of mul so mul = kN
// we have to figure out N here
for (int d: listDivs(mul)) if (d >= 2 && collisions({d, d * 2}) == 1) {
return d;
}
} else {
mul = 1;
s.clear();
}
}
}
return 0;
}
signed hack () {
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> dist(1, (int)1e18);
set<int> s;
for (int i = 0; i <= 200'000; i++)
s.insert(dist(rng));
vec<int> v(all(s));
auto [x, y] = solve(v);
// so now x = pN + k
// and y = qN + k
// so then abs(x - y) = (p - q)N
// and then just go through the divs
int mul = abs(x - y);
for (int d: listDivs(mul)) if (d >= 2 && collisions({d, d * 2}) == 1) {
return d;
}
return 0;
}
#ifdef LOCAL
signed main() {
cin.tie(nullptr)->sync_with_stdio(0);
while (true) {
n = rand() % 1'000'000 + 2;
calls = 0;
int ans = hack();
if (n == ans && calls <= 1000'000) {
cout << "Done " << n << endl;
} else {
cout << n << " " << ans << " " << calls << endl;
}
}
}
#endif
