hexor's blog

Factorial Problem
By hexor, 10 years ago, In English

What can I calculate N! for N<=10^9?

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

»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Factorial grows exponentially, which means that 109! will have enormous amount of digits (linear of N, at least) and you won't be able to output or even store such big number.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I guess he meant to use modulo

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 4   Vote: I like it +3 Vote: I do not like it

      even then, computing (for ) will result in TLE!
      unless he intends to use it to find (small , possibly big ), i don't think his problem is solvable.

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

If you want to get factorial by some modulo, you can do it in . Just precalc factorial in some checkpoints like , , , etc and then start calculating from the checkpoint.

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

Interesting how to find i-th number of (n!)?

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

http://e-maxx.ru/algo/modular_factorial O(M log N)

→ Reply