#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 (i != sqrt(tam)) divs.pb(tam / i); } reverse(all(divs)); while (sz(divs)) { if (collisions({divs.back() + 1, 1})) { if(collisions({tam/divs.back()+1,1})) return tam/divs.back(); 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() + mid, v.end()), u)) v = vector(v.begin() + mid, v.end()); else v.resize(mid); } return calc(v[0], u[0]); }