My brute force was too brute 
Here is how I derived the formula:
https://discuss.codechef.com/questions/98129/your-approach-to-solve-sandwich/98220
2 Likes
““Notice that we take out precisely (⌊x⁄pi⌋!)*pi out of the factorial””
Say x = 6. and p = 2.
(⌊x⁄pi⌋!)*pi = 12 now. But 6! has 16 as power of 2 . Am i right or wrong ??
@sanket407 The thing is we are taking out all the terms divisible by 2 out of 6!, not just the powers of 2.
These terms are 2,4 and 6. We are ignoring these terms as they have 2 as a factor.
The term that we are taking away is hence (⌊x⁄pi⌋!)×(pi^⌊x⁄pi⌋) (Sorry for the typo).
This is equal to 2×4×6 = 48 = 3! × 2^3.
So I calculate 6!/48 = 15
Note that 15 has no powers of 2.
Now as we ignored 2×4×6, it can be written as 3! * 2^3.
We remove the powers of 2 and do the same thing again for 3!
This gives us 3.
15×3=45
This is precisely 6! without any power of 2
1 Like
That’s actually the generalized Lucas theorem (aka Granville theorem), seems like you were able to derive it during the contest, and that’s brilliant!
1 Like
@hikarico I just read it. It really is the same. I actually didn’t derive it completely on my own. Just didn’t realize that this link that I referred to described the basic insight behind the generalized lucas’s theorem. https://goo.gl/JLyjAa
1 Like
@equlnox Learnt , Coded And Passed !! Thanks !! btw your explanation was very good and code was well written too !! Easy to understand !!
Can you shed some light on why that identity (the product of all integers from 1 to p that are co-prime to p is either 1 or -1)is true?
I don’t understand how being an abelian group is the reason for it. Is this a known identity?
1 Like
Yes. Being an abelian group helps because it tells that the group operations are commutative in nature. So, we can take all the x_i's with their inverses together and get the identity element from it. However, there will two elements in our group whose inverse element will be itself the element itself, we have to take care[which gives rise to ±1], it’ll be 1 and p^k - 1. Actually, this theorem is popularly known as Gauss’s theorem who generalized Wilson’s theorem on the finite groups. Here’s a link to that.
https://integermiscellany.wordpress.com/2015/07/23/generalizing_wilson/
1 Like
Thanks, didn’t know about general Wilson theorem before. But you didn’t explained something. Why you wrote (n/p)! instead of (n/p^k)! in recursive formula for n! mod p^k ?
Edit: Found explanation of this here:
How can you know the answer would be (N/K +R)cR?