Блог пользователя mr_warlock

Автор mr_warlock, история, 20 месяцев назад, По-английски

I am stuck on this following problem:

Statement:

Given n, r, x and P where P is a PRIME number.

Print the value nCr % P^x

Constraints:

1 <= r <= n <= 1e12
2 <= x <= 20
2 <= P^x <= 1e6

Thanks for reading the problem. It will be really helpful if you can give me a solution.

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

When we try to find out (a * b) % m, then ((a % m) * (b % m)) % m will also give the same answer. Because it follows the commutative property. But during (a / b) % m if we do ((a % m) / (b % m)) % m, it will give us the wrong answer. Because it does not follow the commutative property.

In your case nCr = n! / (r! * (n — r)!). So to find this answer with mod. You need to use modular inverse. Learn modular inverse first. Then you will understand everything.

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

I've got good news and bad news. The good news is that this paper has the answer, and is an interesting read overall. The bad news is that the authors really did not write with programmers in mind.

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится
»
20 месяцев назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +1 Проголосовать: не нравится

It can be solved by exLucas algorithm. To study it, search on the Internet.

ExLucas can solve $$$\binom nm\mod p$$$ of any $$$0\le m\le n$$$ and $$$0 \lt p\le 10^6$$$.

This is my code if you want to have a look.

If anybody found mistake in code, feel free to reply.

exLucas