rogernadal's blog

Atcoder beginner contest problem — A bit Mathy — Need help
By rogernadal, history, 2 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 (7)
»
2 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
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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;
    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Now you helped me a lot. Thanks!

          → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help with Problem C of this contest?

https://atcoder.jp/contests/abc114/tasks/abc114_c

→ Reply