### I_love_Saundarya's blog

By I_love_Saundarya, history, 4 years ago, Here is the link to the problem:- https://www.spoj.com/problems/FACTMODP/ Comments (41)
| Write comment?
 » Try what’s described here. https://codeforces.com/blog/entry/63491
 » 4 years ago, # | ← Rev. 2 →   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.
•  » » Seems like you are new to competitive programming. Its not possible to run a loop till 10^11.
•  » » » This technique is called contant array and it's a very important technique. You 're too fucking stupid.
•  » » » » I have pity on your shit life. Keep blabbering bad words as they define who you are . Keep up.
•  » » » » » OMG. You 're a bad word.
•  » » » » » » can you explain contant array technique? I do not understand sorry
•  » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   .
•  » » » » good luck storing a 10 ^ 11 array.
 » Divide&Conquer + NTT + FFT
•  » » Please explain it more clearly.
•  » » » The problem doesn't have a solution!!!!!!!!!!! The solution is absolutely incorrect! Shut up tzc_wk. Stop lying! You're a 822E - Liar!
•  » » » » It has. 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.
•  » » » » » Why do you repeat it again?
•  » » » » » And there's a grammar mistake. It should be "It does" instead of "It has".
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   You get the meaning then its ok.
•  » » » You're a SolarFlea!
•  » » » » You're a PolarFlea!
•  » » » » You'd better shut up
•  » » » » » You'd better shut up too.
•  » » » » » » Shut up SolarFlea. You are a PolarFlea!
•  » » I think you don't know how to do it.
•  » » » Are you crazy?!!
 » The problem is too hard that it is of no use to let a cyan to solve the problem! HAHAHAHA
 » 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.
•  » » Or segment tree.
•  » » » Segment tree? U r making me laugh.
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   Why not? We use Segment Tree to calculate [1..sqrt(n)]'s Point Value in O(sqrt(n)log^2).
•  » » » » » Or link-cut-tree.
•  » » » » » » link-cut-tree? U r making me laugh.
•  » » » » » » » /bx cnnfls_csy
•  » » » » » » » » why downvote? he is actually another account of cnnfls_csy. you can see that in submission https://codeforces.com/contest/1720/submission/168832594, despite the template, the remaining part is very similar to cnnfls_csy's code.
•  » » » » » » » » » Actually not. In fact SolarFlea is another account of Alex_Wei. You can see this submission using Alex_Wei's coding style.
•  » » » » » » » » » Actually not. He is the sum of all OIers in NFLS who competed in NOI2022. https://codeforces.com/contest/1734/submission/175218475
•  » » How do you get the values at those points quickly? P(1) and P(1+sqrtp) and so on
•  » » » There is a tool of getting polynomial values at many points. You can just search it on the internet.
 » 4 years ago, # | ← Rev. 2 →   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.
•  » » 12 months ago, # ^ | ← Rev. 2 →   $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