wjex09's blog

SPOJ : TMB
By wjex09, history, 5 years ago, In English

Hi I'm unable to solve the following problem spoj problem . I've tried but can't deduce anything , any hints/ideas are welcome.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone?

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I can suggest you the following strightforward approach:

  • derive or find the exact formula $$$S(n) = \Large \sum\limits_{d|n} \frac{n!}{d!\,(\frac{n}{d}!)^d}$$$
  • represent large numbers as its prime factorisation; i've used
struct component
{
  short cnt[1229];
};

where 1229 is the number of prime numbers till 10000 ($$$N_{max} \times K_{max}$$$) and cnt is the power of corresponding prime number in order to transform all multiplications and divisions to additions and substractions

  • use optimised bigint library for converting factoring numbers into digital form.
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for replying i finally understood how to derive the formula and got it accepted.

    → Reply