#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;
}
vector<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);
}
signed hack() {
int mul = 1;
vec<int> s;
for (int i = 2; i <= 1'000'000; i++) {
mul *= i;
s.push_back(i);
if (mul > (int)1e6) {
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 i = 2; i <= mul; i++) {
if (mul % i == 0) {
if (collisions({i, 2 * i}) == 1) {
return i;
}
}
}
} else {
mul = 1;
s.clear();
}
}
}
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
