Editorial for Mock CCC '19 Contest 2 J5 - Tudor Drinks Even More Tea
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.
Comments
Honestly, I don't think Waterloo would expect high schoolers to know what Möbius inversion is.
I'm not sure if this is official; it's a mock contest