You are not logged in. Please login at www.codechef.com to post your questions!

×

CN02- Editorial

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

luvvynehh's gravatar image

2★luvvynehh
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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