F - Coprime Present Editorial by en_translator


For any distinct pair of integers \(n > m\) between \(A\) through \(B\) (inclusive), \(GCD(n,m)=GCD(n-m,m)\leq n-m \leq B-A\). So, if \(n\) and \(m\) are not pairwise coprime, then both \(n\) and \(m\) are a multiple of an integer between \(2\) and \(B-A\), inclusive.

Therefore, a set satisfies the conditions if and only if, for any integer \(d\) between \(2\) and \(B-A\), inclusive, the set contains at most one multiple of \(d\). Also, we can assume that \(d\) is a prime.

One can find the answer with a bit DP, where the combination of primes are retained as the state, in a total of \(O(N2^{\pi(N)})\) time, where \(N=B-A\) and \(\pi(N)\) denotes the number of primes less than or equal to \(N\). There are at most \(20\) primes that are less than \(72\) (the maximum of \(B-A\)), so this solution is fast enough.

posted:
last update: