Please share how you approached solving SANDWICH, even if you didn't get AC. It will help us to understand how to tackle more mathematically oriented problems. asked 18 May '17, 15:47

First thing which you have to see that Answer is $^{n+n*KN1}C_{n1}$ where $n=\lceil \frac{N}{K} \rceil$ Now for N as large as $10^{18}$ and $M$ nonprime, you will have to use the generalization of Lucas theorem for prime powers. And after calculating answer modulo all the prime powers present in $M$, you will have to use Chinese remainder theorem. Lucas theorem for prime powers is Theorem 1(page 2) in this research paper. answered 18 May '17, 16:14
1
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 !!
(18 May '17, 16:56)
@sanket407 nCr % p^q has to be calculated using Lucas theorem for prime powers
(18 May '17, 17:01)
how ?? p^q is non prime right ?? lucas theorem works for only prime modulus right ?? Correct me if wrong !!
(18 May '17, 17:05)
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
(18 May '17, 18:06)

I didn't use lucas theorem. I just solved it using CRT and by finding Modular multiplicative inverses. Note that if x! and (n1)! don't have any factors of p_{i} then they would have unique answered 18 May '17, 17:38
""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 ??
(19 May '17, 16:54)
1
@sanket407 The thing is we are taking out all the terms divisible by 2 out of 6!, not just the powers of 2.
(19 May '17, 18:14)
1
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!
(19 May '17, 21:50)
1
@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
(19 May '17, 23:35)
@equlnox Learnt , Coded And Passed !! Thanks !! btw your explanation was very good and code was well written too !! Easy to understand !!
(20 May '17, 12:24)

${\frac{n}{k}  {n \% k} + k} \choose {\frac{n}{k}}$ is the solution for the sandwich problem. Honestly this came as an observation rather than some Mathematics. Once this is identified, the problem becomes more of the optimization problem. Things you need for solving this.
Refer https://arxiv.org/pdf/1301.0252.pdf for General Lucas Theorem. Here is a implementation of CRT > http://www.geeksforgeeks.org/chineseremaindertheoremset2implementation Vote this answer, if you feel like. Karma needed for asking questions answered 18 May '17, 16:19
Can you please provide some source to read about Lucas Theorem and CRT?
(18 May '17, 17:14)
1
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 :)
(18 May '17, 17:30)
1
@c0d3h4ck3d Updated the answer with resources for both. @vijju123 It was more of an observation, after writing a brute force algorithm.
(18 May '17, 17:48)
My brute force was too brute :/
(18 May '17, 18:15)
2
Here is how I derived the formula: https://discuss.codechef.com/questions/98129/yourapproachtosolvesandwich/98220
(18 May '17, 18:49)

Nobody seems to have shed some light on how to calculate $\binom{a}{b}\ mod\ (p^k)$. We don't need any research paper to calculate that just some group theory. First let us get rid of all the prime powers of p in $\binom{n}{r}$. Now let us consider a finite group where $X = \{ x : x < p^k, gcd(x, p^k) = 1 \}$. Now we can see that this is abelian group [commutative group] under multiplication. So, we can see that if we multiply all the elements of this group and take $mod\ (p^k)\ i.e\ x_1.x_2.x_3...x_i.. = 1\ if\ p^k = 4\ or\ p^k\ is\ power\ of\ odd\ prime\ and\ +1\ otherwise$. Now to calculate $n!\ mod\ p^k$[remember we've got rid of all the prime powers earlier], we see $n!\ \equiv (\pm 1)^{\dfrac{n}{p^k}}.(1.2.3..(n\ mod\ p^k)). (n / p)!\ (mod\ p^k)$. This is a simple recursive equation which we can calculate in $O(p^k\ log\ n)$ time. Similarly calculate $(n  r)!\ \&\ (r!)$. Take their inverses using extended euclidean and apply chinese remainder theorem. answered 18 May '17, 17:46
1
Can you shed some light on why that identity (the product of all integers from 1 to p that are coprime 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?
(29 May '17, 22:49)
1
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/
(31 May '17, 08:33)

@shashank96,(https://discuss.codechef.com/questions/98129/yourapproachtosolvesandwich?page=1#98152) answered 18 May '17, 18:49

Sandwich is pure math. You can easily determine number of pieces you must cut your sandwich, let's call it T. Now imagine that you cut a sandwich of length l=k*T. That sandwich can be cut only one way and l>=n. Now to produce all ways to cut our original sandwich we must distribute (ln) "shortenings by one" between T pieces. That is "Stars and bars" problem https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics). Now you only need to know how to calculate C(n0, k0) modulo M for very large n0 and k0 (not n and k from a problem, but easily derived from them). For that we need to factorise M. Now suppose that M have some prime divisor p1 and M is divisible by pow(p1, k1), but not divisible by pow(p1, k1+1). Let n0!=pow(p1, t1)q1, where q1 and p1 are coprime. We need to calculate t1 and q1 modulo pow(p1, k1) for each prime divisor of M. (emaxx has similar algorithm, although not exactly one needed). After that we can use Chinese Remainder Theorem and reprsent n!=pow(p1, t1)pow(p2, t2)...pow(pi, ti)Qn, where Qn and M are coprime (we don't need Qn itself, only Qn modulo M). We must do previous part for all three factorials and then divide one by two others (subtract powers for prime divisors and divide in ring for Qn's) answered 18 May '17, 16:19

For 50 pts : Python users could use this inbuilt function scipy.misc.comb(N, R, exact=True) as mentioned in my solution : Python However for 100 pts the topic involved were 1. Lucas Theorem 2. Chinese Remainder Theorem 3. Wilson Theorem which gave an AC and can be referred by link mentioned in my Java code : here answered 18 May '17, 16:36

Two more links: Combinatorics  Mathematics Stack Exchange: nCr  HackerRank: http://m00nlight.github.io/algorithm/2015/04/11/hackerrankncr answered 18 May '17, 17:29
Thank you ymondelo20
(18 May '17, 17:37)

Hi guys! Here is a video editorial by @jtnydv25 on the problem. answered 29 May '17, 01:01

Basically you needed to use generalized lucas's theorem. First covert the solution to aCb form where Now, I could solve it for 50 pnts as I couldn't understand generalized lucas's theorem but here are some links to calculate nCr % m https://discuss.codechef.com/questions/3869/bestknownalgosforcalculatingncrm You can google for more. answered 18 May '17, 15:56
Thanks, mathecodecian :)
(18 May '17, 17:53)
