CN02- Editorial

cn02
coni2015
editorial
simple

#1

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.

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