#include "hack.h"
#include <vector>
using namespace std;
#define F(i, a, b) for(int i = a; i < b; i++)
#define FE(i, a, b) for(int i = a; i <= b; i++)
#define FF(i, a, b) for(int i = a; i > b; i--)
#define FFE(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define ll long long
int skip = 27386;
bool check(vector<ll> a, vector<ll> b){
vector<ll> c = a;
c.insert(c.end(), b.begin(), b.end());
ll total = collisions(c);
return (total > 0);
}
vector<ll> prime_factorization(ll n){
ll test = 2;
vector<ll> factors;
while(test * test <= n){
if(!(n % test)){
factors.pb(test);
n /= test;
}else{
test++;
}
}
if(n > 1) factors.pb(n);
return factors;
}
int hack(){
vector<ll> a, b;
for(int i = 1; i <= skip; i++){
a.pb(i);
}
for(int i = (1e9/2/skip)*skip; i <= 1e9; i += skip){
b.pb(i);
}
while(a.size() > 1 || b.size() > 1){
if(a.size() > b.size()){
vector<ll> al, ar;
int sz_a = a.size();
F(i, 0, sz_a/2){
al.pb(a[i]);
}
F(i, sz_a/2, sz_a){
ar.pb(a[i]);
}
if(check(al, b)){
a = al;
}else{
a = ar;
}
}else{
vector<ll> al, ar;
int sz_a = b.size();
F(i, 0, sz_a/2){
al.pb(b[i]);
}
F(i, sz_a/2, sz_a){
ar.pb(b[i]);
}
if(check(al, a)){
b = al;
}else{
b = ar;
}
}
}
ll np = b[0] - a[0];
vector<ll> factor = prime_factorization(np);
for(ll p : factor){
np /= p;
if(!collisions({1, np+1})){
np *= p;
}
}
return np;
return 42;
}
