What's especially fascinating is that the core of the problem is a generalization of the totient computation, so understanding the inclusion-exclusion construction of totient is very helpful to the problem, while simply memorizing the formula is a misdirection.

OP missing this point shows that he really was doing this for all the wrong reasons. He should have done FIRST or science bowl instead.