## Editorial for Mock CCC '19 Contest 2 J5 - Tudor Drinks Even More Tea

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

To solve the subtask, loop over all pairs of candidate integers and check if they are relatively prime. To check if two integers and are relatively prime, it suffices to see if there is any number between and which divides both of them.

To solve the problem fully, we'll assume that . If we can solve this problem then we can use inclusion-exclusion to compute the answer for arbitrary values of and . If the number of pairs of relatively prime integers where and is , the answer would then be .

We now need to compute the number of pairs of coprime integers such that and .

For those familiar with Möbius inversion, it can be shown that the desired answer is equal to With a sieve, one can precompute up to in .

For those unfamiliar with Möbius inversion, here is a non-rigorous way to approach the problem. One can start by trying to count all pairs of integers which are not relatively prime. One way to get started is by counting how many pairs of integers have 2 as a common factor, then 3, then 5, and enumerating all the primes up to . This produces an overestimate for the number of pairs of integers which are not relatively prime - for example, pairs of integers which have 6 as a common factor have been counted twice in this approach. We can try to compensate for the overcounting by then subtracting away the same count where pairs of integers have as a common factor, for distinct primes and . This, also, is overcounting. Pairs of integers which have 30 as a common factor were included 3 times for 2, 3, and 5, and removed 3 times for 6, 10, and 15. We would therefore need to add these in again.

In effect, we need to enumerate over all integers and count the number of primes that divide them. If is square-free - that is, it is not divisible by for some , then we either add to the count if there are an odd number of prime divisors. Otherwise, the count is even and we subtract.