shrm7pma's blog

nCr for big number

By shrm7pma, 10 years ago, In English

Yesterday i saw a problem in practice section of hackerrank n i tried to solve it but big constraints create problem. Given T testcases , for every test case find nCr modulo 142857 where (n,r) are input for every test case

Constraints: 1 <= T <= 100000 1 <= n <= 1000000000 0 <= r <= n

  • Vote: I like it
  • -14
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If modulo is a prime or product of a prime, you can use Lucas' theorem to achieve this, but 142857 is not a prime...

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes, but 142857=37*3861 where 37 is a prime number. We can compute the answer modulo 37, count the number of times it becomes greater than 36(if it becomes greater than 73 we will count it two times and so on... Note that we keep the counter modulo 3861) and finally print the answer modulo 142857.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are you sure of T's range?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah mentioned constraint are correct

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      In my opinion, this problem is pointless, To achieve this,you need totally math instead of interesting algorithm,so maybe it's a waste of time...I don't know..But if there is an interesting way to do so,please let me know,thanks

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For large n, u can use Lucas theorem, if M is prime..

Since 142857 is not, u will have to reconstruct steps in Lucas theorem using Chinese remainder theorem.

Well explained here:

http://discuss.codechef.com/questions/3869/best-known-algos-for-calculating-ncr-m

→ Reply