#include <bits/stdc++.h> #include "hack.h" #define int long long using namespace std; #define pb push_back #define pf push_front #define mp make_pair #define fi first #define se second #define all(x) (x).begin(), (x).end() typedef long double ld; typedef long long ll; typedef pair<ll,ll> pll; typedef pair<int,int> pii; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<bool> vb; typedef vector<vector<int>> vvi; typedef vector<vector<bool>> vvb; typedef vector<vector<ll>> vvll; typedef vector<string> vs; typedef vector<vector<string>> vvs; typedef vector<char> vc; typedef vector<vector<char>> vvc; typedef map<int, int> mii; typedef unordered_map<int, int> umii; const int mod = 1e9 + 7; const int inf = INTMAX_MAX; /* 10 67 31912 5131 53187 674319 13 17 3 351728 431 */ vi fact[1000001]; int can[1000001]; void pre() { for (int f = 2; f <= 1e6; f++) { for (int mul = 2*f; mul <= 1e6; mul += f) { fact[mul].pb(f); } } for (int i = 1; i <= 1e6; i++) fact[i].pb(i); } bool done = false; signed hack() { if (!done) { pre(); done = true; } memset(can, 0, sizeof(can)); int lim = 1e6 + 1; for (int it = lim; it >= 2; it--) { if (can[it - 1] == -1) continue; vi x = {1, it}; int y = collisions(x); if (y > 0) { // cout << 1 << " " << it << " matched\n"; int ptr = it - 1; vi facts = fact[ptr]; sort(all(facts)); for (auto &fac : facts) { int f = fac; if (f == 1) continue; if (can[f] == -1) continue; else { // maybe change vi y = {1, f + 1}; if (collisions(y) > 0) { return f; } } } } else { int ptr = it - 1; for (auto &f : fact[ptr]) { can[f] = -1; can[ptr / f] = -1; } } } assert(false); return 10; }