#include <vector>
#include <cmath>
#include <set>
#include <algorithm>
#include <iostream>
#include "hack.h"
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {
if (b == 0) return a;
return gcd(b, a % b);
}
vector<ll> get_all_divisors(ll x) {
vector<ll> divisors;
if (x == 0) return divisors;
ll sqrt_x = sqrt(x);
for (ll i = 1; i <= sqrt_x; i++) {
if (x % i == 0) {
divisors.push_back(i);
if (i != x / i) {
divisors.push_back(x / i);
}
}
}
return divisors;
}
vector<ll> get_divisors_in_range(ll x, ll low_bound, ll high_bound) {
vector<ll> res;
if (x == 0) return res;
ll sqrt_x = sqrt(x);
for (ll i = 1; i <= sqrt_x; i++) {
if (x % i == 0) {
if (i >= low_bound && i <= high_bound) {
res.push_back(i);
}
ll j = x / i;
if (j != i) {
if (j >= low_bound && j <= high_bound) {
res.push_back(j);
}
}
}
}
return res;
}
int hack() {
const ll M_val = 1000000007;
const int k_val = 40000;
vector<ll> v1;
for (int i = 1; i <= k_val; i++) {
v1.push_back(i * M_val);
}
ll col1 = collisions(v1);
if (col1 == 0) {
ll low = 40001, high = 1000000000;
while (low <= high) {
ll mid = (low + high) / 2;
vector<ll> test_vec = {1, 1 + mid};
if (collisions(test_vec) == 1) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return low;
}
set<ll> candidates_T;
for (int L = 1; L <= k_val; L++) {
ll numerator = (ll)L * k_val - col1;
if (numerator <= 0) break;
ll denominator = (ll)L * (L + 1);
if (numerator * 2 % denominator != 0) continue;
ll T0 = (numerator * 2) / denominator;
if (T0 == 0) continue;
if (k_val - 1 < T0) {
if (L == 0) {
candidates_T.insert(T0);
}
} else {
ll L0 = (k_val - 1) / T0;
if (L0 == L) {
candidates_T.insert(T0);
}
}
}
static vector<ll> divisors_M;
if (divisors_M.empty()) {
divisors_M = get_all_divisors(M_val);
}
vector<ll> candidate_list;
for (ll T0 : candidates_T) {
for (ll g : divisors_M) {
if (M_val % g != 0) continue;
ll M_div_g = M_val / g;
if (gcd(T0, M_div_g) != 1) continue;
ll candidate_n = g * T0;
if (candidate_n > (ll)1e18) continue;
candidate_list.push_back(candidate_n);
}
}
vector<ll> passed_candidates;
for (ll cn : candidate_list) {
vector<ll> test_vec = {1, 1 + cn};
if (collisions(test_vec) == 1) {
passed_candidates.push_back(cn);
}
}
if (passed_candidates.empty()) {
ll low = 2, high = 1000000000;
while (low <= high) {
ll mid = (low + high) / 2;
vector<ll> test_vec = {1, 1 + mid};
if (collisions(test_vec) == 1) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return low;
}
ll G_val = passed_candidates[0];
for (int i = 1; i < passed_candidates.size(); i++) {
G_val = gcd(G_val, passed_candidates[i]);
}
vector<ll> divisors_G = get_divisors_in_range(G_val, 2, min(G_val, (ll)1000000000));
ll best_candidate = -1;
for (ll d : divisors_G) {
ll g_d = gcd(d, M_val);
ll T_d = d / g_d;
ll q = k_val / T_d;
ll r = k_val % T_d;
ll term1 = T_d * (q * (q - 1) / 2);
ll term2 = r * q;
ll expected_col = term1 + term2;
if (expected_col != col1) continue;
vector<ll> test_vec = {1, 1 + d};
if (collisions(test_vec) != 1) continue;
if (d > best_candidate) {
best_candidate = d;
}
}
if (best_candidate == -1) {
ll low = 2, high = 1000000000;
while (low <= high) {
ll mid = (low + high) / 2;
vector<ll> test_vec = {1, 1 + mid};
if (collisions(test_vec) == 1) {
high = mid - 1;
} else {
low = mid + 1;
}
}
best_candidate = low;
}
return best_candidate;
}
