Moodular Arithmetic

Revision en1, by vkditya0997, 2016-07-18 10:34:57

Hello Codeforces,

I was trying this 603B - Moodular Arithmetic, I couldn't get the idea and read the editorial.

I have a doubt.

for k >  = 2 case :

we choose m such that km = 1 mod p

and also it has been proved that f(ki * n mod p ) = ki * f(n) mod p

and now if we choose some f(n) , we get the value of f(n) , f(k * n mod p ) ,.... f(km - 1 * n mod p )

Understood until this point

I didn't understand from here..

Therefore, if we choose f(n) of p - 1 / m integers n, we can get value of all p-1 non-zero integers. Since f(n) can be chosen in p ways for each of the p - 1 / m integers, the answer is pp - 1 / m

Can someone please help in understanding this one?

Thanks in Advance!

Tags advanced math, graph, #contest


  Rev. Lang. By When Δ Comment
en1 English vkditya0997 2016-07-18 10:34:57 839 Initial revision (published)