By rogernadal, history, 2 years ago,

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 ?

• 0

 » 2 years ago, # | ← Rev. 2 →   0 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.
•  » » 2 years ago, # ^ |   0 Thanks ! Can you explain why the calculation is like this ? How do we determine, the last 3 lines below. I think, it may be to account for double counting, but it's not very clear to me. long ans = num75; ans += num25 * (num3-1); ans += num15 * (num5-1); ans += num5 * (num5-1) * (num3-2) / 2; 
•  » » » 2 years ago, # ^ |   0 The above 3 lines I am interested to understand comes from this submission based on the same idea : https://beta.atcoder.jp/contests/abc114/submissions/3706081
•  » » » » 2 years ago, # ^ |   0 Here is the explanation, I received through another source : If you take a prime appearing >= 24 times you need a different prime appearning >= 2 times. So it's num25 * (num3 — 1) Because num3 covers all num25.For last example -> The position of / 2 is sort of misleading, it's actually (num5 choose 2) * 3 = (num5 * (num5 — 1) / 2) * num3
•  » » » » » 9 months ago, # ^ |   0 Now you helped me a lot. Thanks!
 » 6 months ago, # |   0 Can anyone help with Problem C of this contest?https://atcoder.jp/contests/abc114/tasks/abc114_c
•  » » 2 months ago, # ^ |   0 you can use depth-first search to generate all seven five three numbers and check if it is <= n submission_link