rogernadal's blog

Atcoder beginner contest problem — A bit Mathy — Need help
By rogernadal, history, 5 years ago, In English

I was trying to solve the problem : https://beta.atcoder.jp/contests/abc114/tasks/abc114_d The editorial is not in English and google translate didn't help much.

Can someone please suggest the idea which is used to solve the problem ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

A number has exactly 75 divisors if its prime factorization is one of these forms: p^74, p^2*q^24, p^4*q^14, p^2*q^4*r^4. The ways correspond to 75, 3*25, 5*15, 3*5*5 which are all 75. For every prime up to N, count the number of times it divides N!. Then you can do simple nested loops to check all possible choices for each pattern.

→ Reply