#include <bits/stdc++.h> #define ll long long #define pb push_back #define f first #define s second #define sz size() using namespace std; ll collisions(vector<ll> x); bool ask(const vector<ll>& v, const vector<ll>& u){ vector<ll> q; q.reserve(v.sz+u.sz); for(auto i:v){q.pb(i);} for(auto i:u){q.pb(i);} ll k = collisions(q); return k>0; } ll solve(ll x) { ll n=x, di=x; for(ll p=2; p*p <= di; p++){ while(di%p==0){ ll cand=n/p; if(n%p==0 && cand>=2 && collisions({1, cand+1})>0){ n/=p; } di/=p; } } ll cand=n/di; if(n%di==0 && di>1){ if(collisions({1,cand+1}) > 0) n=cand; } return n; } int hack(){ ll mx=(ll)(1e9); const int b = 10007; vector<ll> v,u; for(int i = 1; i <= b; i++){ v.pb(i); } for(ll x = ((mx>>1)/b)*b; x <= mx+b; x+=b){ u.push_back(x); } while(v.sz > 1 || u.sz > 1){ if(v.sz < u.sz){ swap(v,u); } int mid=(v.sz>>1); vector<ll> l(v.begin(),v.begin()+mid); vector<ll> r(v.begin()+mid,v.end()); if(ask(l,u)){ v.swap(l); }else{ v.swap(r); } } //return llabs(v[0]-u[0]); -> es multiplo pero no necesariamente n return solve(llabs(v[0]-u[0])); }