#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
long long collisions(vector<long long> x);
bool does_n_divide(long long d) {
vector<long long> x = {1, 1 + d};
return collisions(x) == 1;
}
bool is_nB_le(long long B, long long K) {
if (K <= 0) return false;
vector<long long> x;
long long val = B;
for (long long i = 0; i <= K; ++i) {
x.push_back(val);
val += B;
}
return collisions(x) > 0;
}
long long find_nB(long long B, long long limit) {
long long lo = 1, hi = limit;
long long ans = limit;
while (lo <= hi) {
long long mid = (lo + hi) / 2;
if (is_nB_le(B, mid)) {
ans = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return ans;
}
long long get_exponent(long long B, long long p) {
long long e = 0;
long long max_e = 1;
long long tmp = p;
while (tmp <= 1000000000LL / p) {
tmp *= p;
max_e++;
}
long long lo = 0, hi = max_e;
while (lo < hi) {
long long mid = (lo + hi + 1) / 2;
long long power = 1;
for (long long i = 0; i < mid; ++i) {
if (power > 1000000000000000000LL / p) {
power = -1;
break;
}
power *= p;
}
if (power == -1 || does_n_divide(B * power)) {
lo = mid;
} else {
hi = mid - 1;
}
}
return lo;
}
vector<long long> get_primes(long long limit) {
vector<bool> is_prime(limit + 1, true);
vector<long long> primes;
for (long long i = 2; i <= limit; ++i) {
if (is_prime[i]) {
primes.push_back(i);
for (long long j = i * i; j <= limit; j += i)
is_prime[j] = false;
}
}
return primes;
}
int hack() {
long long total_cost = 0;
const long long SMALL_LIMIT = 5000;
{
vector<long long> x;
for (long long i = 1; i <= SMALL_LIMIT + 1; ++i) x.push_back(i);
if (collisions(x) > 0) {
long long lo = 2, hi = SMALL_LIMIT;
while (lo < hi) {
long long mid = (lo + hi) / 2;
vector<long long> y;
for (long long i = 1; i <= mid + 1; ++i) y.push_back(i);
if (collisions(y) > 0) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
}
long long B = 1;
vector<long long> primes = get_primes(31623);
for (long long p : primes) {
long long e = get_exponent(B, p);
if (e > 0) {
long long power = 1;
for (long long i = 0; i < e; ++i) power *= p;
B *= power;
}
}
if (does_n_divide(B)) {
return B;
}
long long K = 100000;
while (K <= 1000000000) {
if (is_nB_le(B, K)) break;
K *= 2;
}
long long hi = K;
long long lo = 31623;
while (lo < hi) {
long long mid = (lo + hi) / 2;
if (is_nB_le(B, mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
long long p = lo;
return B * p;
}
