### 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/

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