dreamplay's blog

By dreamplay, 9 years ago, In English

I have often encountered problems(in gym) which reduce to finding C(n,r) % p , where p is not necessarily prime . Also n and r are both large . Essentialy they demand for the use of Lucas and Chinese Remainder Theorem.

For constraints let`s take this problem .

This link does help a lot but I am still confused , especially in the part which asks to use C.R.Theorem . How to apply CRT?

Also what if p is not a square free number ?

Along with explaination , a link to code would be extremely helpful.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Let m and n be coprime, , and . Then x = ms + a = nt + b where s and t are unknown. Rewrite this as ms - nt = b - a. On the other hand, we can find k and l such that mk + nl = 1, so mk(b - a) + nl(b - a) = b - a. Subtracting the equalities, we get that m(kb - ka - s) + n(lb - la + t) = 0, so kb - ka - s is divisible by n, and mk(b - a) - ms is divisible by mn. So, .