Can anyone post the editorial of MCQ game problem (T-24)from Innerve Summer of Code Challenge ?

I have gone through a lot of successful submissions for MCQ game problem but still not able to understand them ,specially why mod has been changed to mod-2.Please help.

See this:

People have used this to calculate the modular inverse, and this is the reason you see mod - 2 in their codes.

Got it.Thanks a lot :slight_smile:

Can someone explain how did we arrive with inverse modulo as I am not able to get the logic behind the problem completely :frowning: Please help !!

Explanation of using the modular inverse:

In problem T24 “MCQ Game”, we want to calculate k+k^2+\cdots+k^n = k(k^n-1)/(k-1) but with k^n-1 being huge, we only calculate the value (k^n-1) \bmod m. So to make the division by (k-1), we need to find the modular inverse of this, which is the number j that gives (k-1)\cdot j \equiv 1 \bmod m.

There are two ways to find this. The one given depends on the fact that m is prime, so by Fermat’s Little Theorem we must have a^{m-1}\equiv 1 \bmod m (provided m doesn’t divide a). This immediately gives us b, the inverse of a, must be b\equiv a^{m-2}\bmod m since then a\cdot b \equiv a\cdot a ^{m-2} = a^{m-1}\equiv 1 \bmod m

If we don’t know that m is prime, there may still be a modular inverse. We can find this with the extended Euclidean algorithm which is actually often a faster method anyway. If we want, this can give both inverses simultaneously, inverse of a \bmod m and inverse of m \bmod a.

It’s apparent that dividing by (k-1) won’t work for k=1. Then we should be totalling n rounds of 1 question each - always correct - to give an answer of n, but unfortunately the test set erroneously expects a value of 1. My answer coping with this error

1 Like