#include "hack.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<ll>; const int R = 1e6; ll f(ll N) { ll r = R % N, k = R / N; ll ans = 1LL * r * k * (k+1) / 2; ans += 1LL * (N-r) * k * (k-1) / 2; return ans; } int hack(){ int l=1, r=R; vi v; for(int i=1; i<=R; ++i) v.push_back(i); ll x = collisions(v); while(l < r) { int mid = (l+r)/2; if(f(mid) == x) return mid; if(f(mid) > x) l = mid+1; else r = mid-1; } return r; }