#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 */ signed hack() { mii can; int i = 1e6; for (int it = i; it >= 2; it--) { if (can[it] == -1) continue; vi x = {1, it}; int y = collisions(x); if (y > 0) { int ptr = it - 1; // cout << "1 " << ptr << " gives a match\n"; vi facts; for (int f = 1; f * f <= ptr; f++) { if ((ptr % f) != 0) continue; facts.pb(f); facts.pb(ptr/f); } sort(all(facts)); // for (auto &fac : facts) cout << fac << " "; // cout << '\n'; 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 (int f = 2; f * f <= ptr; f++) { if ((ptr % f) != 0) continue; can[f] = -1; can[ptr / f] = -1; } } } return 10; }