The totient formula isn't the hard part of the problem.
The test has a very short time limit (for the difficulty of the problems), and has many gruelingly complicated problems,so if you dont have the formulas down cold, you'll burn out during the contest.
Of course, if you don't care about silly speed-mathing contests, you can enjot the problems at a leisurely pace.
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.
Completely agree, I also liked the problem and thought it was conceptual as far as these things go.
Asking for N mod 1000 was another cute twist that was meant to get you thinking about the divisibility properties of the totient function - "hmm, so (p-1) always divides \phi(n) for all prime factors p of n, how convenient..."
That's a cute coincidence that 1000 divides (11-1)(101-1), but I doubt it was intentional. The test writers didn't have much choice unless they chose a different base than 5+5.
https://artofproblemsolving.com/wiki/index.php/2022_AIME_I_P...
The totient formula isn't the hard part of the problem.
The test has a very short time limit (for the difficulty of the problems), and has many gruelingly complicated problems,so if you dont have the formulas down cold, you'll burn out during the contest.
Of course, if you don't care about silly speed-mathing contests, you can enjot the problems at a leisurely pace.