Hello, the solution (https://usaco.guide/problems/poi-2004maximal/solution) details a proof for why we only need the first 70 primes. However, I can’t see how I would come up with the proof myself, especially during a contest.
I could see this happening during the contest: I get MLE, think about which parameters to reduce, realize that large cycles are suboptimal, so I binary search on AC for how many primes I need. Is that what you’re expected to do during the contest, or is this a well known proof technique contestants are expected to know? If the latter, I would greatly appreciate resources to similar proofs.