please help in modulo operator in September Challenge 2014 Chef and Rainbow Array - 2| Solved

During competition i had solved this problem but got wrong answe due to modulo operator. please amend my code and help me in understanding how to handle modulo operator in case of division.
Thanks in advance

Problem link

My Solution link

I think it is giving wrong answer because of your ‘combination’ function. You should note that (a/b) %mod !=(a%mod)/(b%mod).

Have a look at this: Modulo Operation.

You are multiplying 5 consecutive numbers and then dividing it by 5! .

In any two consecutive numbers, one of them is divisible by 2, in 3 consecutive numbers one is divisible by 3. Similarly in 5 consecutive numbers one is divisible by 5. So all you need to do is, instead of dividing after multiplication, divide before multiplication.
Multiply the results and take mod in each step.


Thanks for your reply.

But the problem is that i have to use long long data type and long long data type does not give answer in decimals. So how could i divide before multiplication.

1 solution to my problem would be to use concept of modulo inverse ,but i am unable to understand modulo inverse concept.

You have to check, out of five consecutive numbers which no is divisible by 5. Divide it by 5 and store it. Similarly out of any 4 consecutive of those 5 numbers which number is divisible by 4. Divide it,store it. Do the same for 3 and 2.

Now multiply all five numbers and you can take modulus at every step.

1 Like

Thanks. got accepted !

modulo operator doesnt work well with division… so what we have to do instead is to find the multiplicative inverse of the value… eg:- if n=7,then MMI(mltiplicative inverse) of 4 is 2 since (4*2)%7=1… also the multiplicative inverse should lie within n…ie MMI < n; this will do the trick :wink:

Correct me if I am wrong but from what I remember, for taking MMI in (x/y)%M - y and M should be co prime, which is not necessary in this problem.