So again I am writing a post about ICL2015 Finals. My [last post](http://codeforces.me/blog/entry/18542) was about a DP problem which was not that much hard. But now I am really stuck by a tough [problem](http://codeforces.me/gym/100637/problem/D) (I am mentioning this one as tough because number of people who solved it was really low).↵
↵
What I did for this one? Well, whatever I did to solve this problem was based on [this](http://discuss.codechef.com/questions/3869/best-known-algos-for-calculating-ncr-m) tutorial from CodeChef. You can check that out.↵
↵
↵
In short the problem is:↵
↵
~~~~~↵
Given n,k,m where n,k<=10^18, m<=10^6, we need to find C(n,k)%m where C(n,k) means number of ways to choose k objects from n objects.↵
~~~~~↵
↵
↵
↵
So, the question is: **What did I do to solve this problem?**↵
↵
↵
Following the tutorial, I prime factorized `m`. Eventually, I got some prime numbers as factors. Then I applied **Lucas' Theorem** for each of this prime. After calculating answers for each of this prime, I had to solve some equations of the form `X = A[i] (mod M[i]).` ↵
↵
↵
And these equations can be solved by [Chinese Remainder Theorem.](https://www.youtube.com/watch?v=ru7mWZJlRQg)↵
↵
↵
Now, where did I get stuck? I did all these things mentioned above. But when we are given a prime `m` when **m has prime powers in its factorized form**, I could not find a solution to calculate the required result.↵
↵
↵
**Let me give a quick example.**↵
↵
↵
Imagine, `n=10, k=5, m=12341.` To find `X=C(10,5)%12341`, I first prime factorized `12341.` So `12341=7*41*43.`↵
↵
I applied **Lucas' Theorem** for each of the prime factors. What I got is:↵
↵
↵
~~~~~↵
X = 0 (mod 7);↵
X = 6 (mod 41);↵
X = 37 (mod 43);↵
~~~~~↵
↵
↵
Now my task was to combine this equations to find our `X`. I applied **CRT** for this and got the required answer `252`. **Yahooo!** **:D**↵
↵
↵
But wait, when `m=1000` (or **some number with prime powers**), it didn't work. **:(** ↵
↵
↵
This is where I need a solution. I actually need to calculate `C(n,r)%m` where `m` is of the form `p^a where p is a prime.`↵
↵
↵
As you can realize, I am not quite good. It will be too much helpful if you share your ideas on how to solve the above mentioned problem and give instructions to code it in detail, step by step. And I will be really grateful to you. :)↵
↵
**Sorry for the long post.**↵
↵
**PS1:** I found few ideas on how to get around this problem online. But I could not understand and of course could not code anything.↵
↵
**PS2:** Really sorry for the long post.↵
↵
↵
↵
~~~~~↵
Cheers and thanks in advance!↵
~~~~~↵
↵
↵
What I did for this one? Well, whatever I did to solve this problem was based on [this](http://discuss.codechef.com/questions/3869/best-known-algos-for-calculating-ncr-m) tutorial from CodeChef. You can check that out.↵
↵
↵
In short the problem is:↵
↵
~~~~~↵
Given n,k,m where n,k<=10^18, m<=10^6, we need to find C(n,k)%m where C(n,k) means number of ways to choose k objects from n objects.↵
~~~~~↵
↵
↵
↵
So, the question is: **What did I do to solve this problem?**↵
↵
↵
Following the tutorial, I prime factorized `m`. Eventually, I got some prime numbers as factors. Then I applied **Lucas' Theorem** for each of this prime. After calculating answers for each of this prime, I had to solve some equations of the form `X = A[i] (mod M[i]).` ↵
↵
↵
And these equations can be solved by [Chinese Remainder Theorem.](https://www.youtube.com/watch?v=ru7mWZJlRQg)↵
↵
↵
Now, where did I get stuck? I did all these things mentioned above. But when we are given a prime `m` when **m has prime powers in its factorized form**, I could not find a solution to calculate the required result.↵
↵
↵
**Let me give a quick example.**↵
↵
↵
Imagine, `n=10, k=5, m=12341.` To find `X=C(10,5)%12341`, I first prime factorized `12341.` So `12341=7*41*43.`↵
↵
I applied **Lucas' Theorem** for each of the prime factors. What I got is:↵
↵
↵
~~~~~↵
X = 0 (mod 7);↵
X = 6 (mod 41);↵
X = 37 (mod 43);↵
~~~~~↵
↵
↵
Now my task was to combine this equations to find our `X`. I applied **CRT** for this and got the required answer `252`. **Yahooo!** **:D**↵
↵
↵
But wait, when `m=1000` (or **some number with prime powers**), it didn't work. **:(** ↵
↵
↵
This is where I need a solution. I actually need to calculate `C(n,r)%m` where `m` is of the form `p^a where p is a prime.`↵
↵
↵
As you can realize, I am not quite good. It will be too much helpful if you share your ideas on how to solve the above mentioned problem and give instructions to code it in detail, step by step. And I will be really grateful to you. :)↵
↵
↵
**PS1:** I found few ideas on how to get around this problem online. But I could not understand and of course could not code anything.↵
↵
**PS2:** Really sorry for the long post.↵
↵
↵
↵
~~~~~↵
Cheers and thanks in advance!↵
~~~~~↵
↵
