#include "hack.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define rep(i,a,b) for(int i = a; i <= b; i++) #define per(i,a,b) for(int i = a; i >= b; i--) #define pb push_back int closest_prime(int x) { per(j,x,1) { bool ok = 1; for(int i = 2; i*i <= j; ++i) { if(j%i==0) { ok=0; break; } } if(ok) return j; } return -1; } int hack(){ vector<ll> vals; ll B = 31627, b = 31627; ll N = 1000000000; ll l = 1,r,x; while (1) { vals.clear(); for(ll i = 1; i<=b; i++) { vals.pb(i); } for(ll i = N+1; i<=N+b*b+1; i+=b) { vals.pb(i); } x = collisions(vals); //cout << x << '\n'; if(x>B) { l=1; break; } int L=b*b/(x+1),R=b*b/(x); if(x==1) R = N; //cout << L << ' ' << R << ' ' << x << ' ' << l << '\n'; l += L; b = closest_prime(sqrt(b*b/2)); if(R-L+1 <= 2*B) break; } //cout << "FOUND RANGE: " << l << ' ' << l+B << '\n'; for(ll i = l ; i <= l+2*B; i++) { if(i==0)continue; x = collisions({2*i,i}); if(x==1) { return i; } } for(ll i = B; i<= N; i+=B) { x = collisions({2*i,i}); if(x==1) { return i; } } return -1; }