Contest Duration: - (local time) (100 minutes) Back to Home

## 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: