×

# CN02- Editorial

 0 Problem Code- CN02 Difficulty - Simple Prerequisites: Modular Multiplicative Inverse Mathematics(Permutations and Combinations) Euler's Theorem or Extended Euclidean algorithm Problem: Find the number of integral solutions of the equation 2(a1+a2+a3+a4+a5+a6)+a7=N . a7 can take values from 1 to N-12. Now iterate over all the values of a7 and find the number of solutions, and you have to sum them up. There will be terms of nCr in the solution and you need to compute nCr mod M , to do this efficiently, you will have to use Euler's theorem, or Extended Euclidean Algorithm. http://en.wikipedia.org/wiki/Modular_multiplicative_inverse To compute nCr mod P : Using the Euler's theorem for Modular Multiplicative inverse. nCr mod p can be written as n! / (n-r)!r! mod p which is equal to n! * ((n-r)!r!))^-1 mod p now let x= ((n-r)!r!)) . Now the problem is just to find out what the inverse of x mod p would be . Euler's theorem states that when p is prime then x^-1 mod p = x^(p-2) mod p . This should be easy to calculate using the Modular exponentiation. modular multiplicative inverse Using the Extended Euclidean Algorithm. This allows you to calculate the inverse of x mod p , and it is generally faster than the Modular exponentiation approach when p is large. extended Euclidean Algorithm asked 19 Jan '15, 14:44 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,191
×5
×1

question asked: 19 Jan '15, 14:44

question was seen: 1,245 times

last updated: 19 Jan '15, 14:44