Your approach to solve SANDWICH?

general
,
29

how do u calculate ans modulo all prime powers in M .??

Since prime power can be non prime ( i am assuming prime power means p^q)
So denominator and prime power can be non co prime too right ??
So how do you calculate modular inverse !!

1 Like
30

@sanket407 nCr % p^q has to be calculated using Lucas theorem for prime powers

31

Yes N and K are not 10^18 in that testcase.

32

how ?? p^q is non prime right ?? lucas theorem works for only prime modulus right ?? Correct me if wrong !!

33

Can you please provide some source to read about Lucas Theorem and CRT?

34

so constraints were n,k <= 10^18 or the same as of subtask ,2??

35

How did you identify that (nk−n%k+knk)(nk−n%k+knk) is the solution? I would appreciate if you can explain that as well :slight_smile:

1 Like
36

Thank you ymondelo20

37

Thanks abdullah786 :smiley:

38

@c0d3h4ck3d Updated the answer with resources for both.

@vijju123 It was more of an observation, after writing a brute force algorithm.

1 Like
39

Thanks, mathecodecian :slight_smile:

40

it is, but in a paper of Andrew Granville, it has been extended to prime powers, and after that u need to use chinese remainder theorem

41

My brute force was too brute :confused:

42

Here is how I derived the formula:
https://discuss.codechef.com/questions/98129/your-approach-to-solve-sandwich/98220

2 Likes
43

@prakhariitd Thank you. I lost 50 pts for a small bug :stuck_out_tongue:

44

sad for u @ista2000

45

@equlnox

““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 ??

46

@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
47

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
48

@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