[gowld]

The problem (and linked solution is here)

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.

[junar]

Agree, and to add a bit more context:

* The contest has 15 problems and a time limit of 3 hours, giving only an average of 12 minutes per problem.

* The average score is 4.83/15, from the official statistics [1].

* The statistics noted that only 5.17% of test takers answered this problem correctly, making it the second-hardest problem out of the 15 on the exam.

[1] "AIME 02/08/2022" https://amc-reg.maa.org/reports/generalreports.aspx

[lupire]

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.

[jhshah]

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..."

[chrchang523]

The mod 1000 is actually a consequence of the test format: all answers are integers in [0, 999], you fill in 3 digit-bubbles.

[lupire]

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.