I_love_Saundarya's blog

By I_love_Saundarya, history, 5 years ago, In English

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

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

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

»
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.

  • »
    »
    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.

    • »
      »
      »
      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.

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

Divide&Conquer + NTT + FFT

»
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

»
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.

»
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.

»
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.

  • »
    »
    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

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

in mind