rogernadal's blog

By rogernadal, history, 6 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

| Write comment?
»
6 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.