I_love_Saundarya's blog

How to calculate n!%p for very large 'n' ?

By I_love_Saundarya, history, 5 years ago, In English

Here is the link to the problem:- https://www.spoj.com/problems/FACTMODP/

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

Comments Comments (41)
| Write comment?
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Try what’s described here. https://mirror.codeforces.com/blog/entry/63491

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -32 Vote: I do not like it

I don't know the actually way to implement this problem but you can loop N from 1 to 10^11 and calculate n!%p through this formula: (a * b) % c = ((a % c) * (b % c)) % c; and prefix sum. Then store them into an array. If you implement the problem with these operations, you can get the answer in about 3 hours.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -30 Vote: I do not like it

    Seems like you are new to competitive programming. Its not possible to run a loop till 10^11.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      This technique is called contant array and it's a very important technique. You 're too fucking stupid.

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

Divide&Conquer + NTT + FFT

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

The problem is too hard that it is of no use to let a cyan to solve the problem! HAHAHAHA

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

I have a solution First,build a polynomial of n*(n+1)*(n+2)*(n+3).....*(n+sqrt(p)) Then use we can get the value of the polynomial at 1,sqrt(p)+1,2sqrt(p)+1.... Then we can calculate the rest of part(not exceed sqrt(p)) using bruteforce.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

We can construct a polynomial :

$$$F(x)=\prod_{i=1}^{\lfloor\sqrt n\rfloor}(x+i)$$$

And then we have :

$$$n!=\bigg(\prod_{i=n-{\lfloor\sqrt n\rfloor}^2}^{n}i\bigg)\cdot\prod_{i=0}^{\lfloor\sqrt n\rfloor}F(i\cdot \lfloor\sqrt n\rfloor)$$$

For $$$\prod_{i=n-{\lfloor\sqrt n\rfloor}^2}^{n}i$$$ , we can calculate it use brute force.

For $$$\prod_{i=0}^{\lfloor\sqrt n\rfloor}F(i\cdot \lfloor\sqrt n\rfloor)$$$ , we can use fast polynomial multipoint evaluation to calculate. (https://cs.stackexchange.com/questions/60239/multi-point-evaluations-of-a-polynomial-mod-p)

Sorry for my poor English.

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

if p is prime then the problem is pretty much implementation of wilson's theorem.

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

    $$$n=\lfloor \frac{p}{2} \rfloor$$$ is still big enough to make any naive solution exceed the TL.

    UPD: you're also 3 years late

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

in mind

→ Reply