Your approach to solve SANDWICH?

equlnox · May 18, 2017, 5:38pm

I didn’t use lucas theorem. I just solved it using CRT and by finding Modular multiplicative inverses.

Let n=⌈^N⁄_K⌉

and x = (K × n) - N

So, as we have to distribute x vacancies in n parts, the number of ways is ^n+x-1C_x

Let the prime factorization of M = p₁^e1×p₂^e2×p₃^e3×p₄^e4 …×p_t^et

Here t is the total no of unique prime factors.

Here p_i^ei and p_j^ej are coprime for any 1 ≤ (i≠j) ≤ t

So if we find ^n+x-1C_x Mod p_i^ei for each i,
We can then combine the results to find ^n+x-1C_x Mod M using CRT

Note that if x! and (n-1)! don’t have any factors of p_i then they would have unique

modular multiplicative inverse.

The main issue that we face now is that (n-1)! and x! could have factors of p_i

Let y be the highest power of p_i which divides x!

Then let F(x,p_i^ei) = ((x!)/p_i^y) Mod p_i^ei
As F(x,p_i^ei) is not divisible by p_i, we can find its modular multiplicative inverse.

We can later on deal with the total power of p_i in ^n+x-1C_x and multiply it to our answer.

So ^n+x-1C_x Mod p_i^ei will be (p_i^z × F(x+n-1,p_i^ei))/(F(x,p_i^ei) × F(n-1,p_i^ei)) Mod p_i^ei

Here z is the highest power of p_i which divides ^n+x-1C_x

To find F(x,p_i^ei), the trick here is to take all the numbers divisible by p_i out of the factorial.

Notice that we take out precisely (⌊^x⁄_{p_i}⌋!)×p_i^⌊x⁄pi⌋ out of the factorial.

Now let H = x!/((⌊^x⁄_{p_i}⌋!)×p_i^⌊x⁄pi⌋) Mod p_i^ei
(Note: H is basically x! with all terms divisible by p_i ignored)

H can be found in in O(p_i^ei+ log x) using fast exponentiation as

all numbers in the factorial repeat after p_i^ei numbers Mod p_i^ei

Now we can say that F(x,p_i^ei)=H×F(⌊^x⁄_{p_i}⌋,p_i^ei)

This is a recurrence relation, so the over all complexity is O((p_i^ei+log x)×(log x))

We now know how to find F(x,p_i^ei)

Now we need to know how to find the power of p_i in x!.

This is simply Σ ⌊^x⁄_{p_i^c}⌋ where c is a natural number.

PS:- The recursive part can be optimized by making it iterative.

That reduces the overall complexity to O(M + (log²(N+k)×(log M)))