#include <bits/stdc++.h> #define ll long long #define sz(x) int(x.size()) #define all(x) x.begin(),x.end() #define fr first #define se second #define pb push_back using namespace std; long long collisions(std::vector<long long> x); bool can(vector<ll>v, vector<ll>u) { map<ll,ll>used; for(auto k:v) used[k]=1; for(auto k:u) if(used[k]) continue; else { used[k]=1; v.pb(k); } return collisions(v); } ll calc(ll x, ll y) { if(x>y) swap(x,y); ll tam=y-x, i; vector<ll>divs; for(i=2; i<=sqrt(tam); i++) { if(tam%i!=0) continue; if(collisions({1+i,1})) return i; if(i!=sqrt(tam)) divs.pb(tam/i); } while(sz(divs)) { if(collisions({divs.back()+1,1})) return divs.back(); divs.pop_back(); } return tam; } const ll maxM=1e9, prim=14009; //const ll maxM=1e1, prim=3; int hack(){ ll i, j; vector<ll>v(prim), u; iota(v.begin(),v.end(),1); for(i=((maxM/2)/prim)*prim; i<=maxM+prim; i+=prim) u.pb(i); while(sz(v)>1||sz(u)>1) { if(sz(v)<sz(u)) swap(v,u); ll mid=sz(v)/2; if(can(vector(v.begin(),v.begin()+mid),u)) v.resize(mid); else v=vector(v.begin()+mid,v.end()); } return calc(v[0],u[0]); }