NMNMX - Editorial

editorial
, ,
9

Since 1=a0 for any a, we could say that a^x=a^x(modp−1)(modp).

I am trying but not able to figure out how the statement comes out of Fermat’s little theorem and the fact that a raised to 0 becomes 1.

Can someone please elaborate?

10

For people having difficulty in understanding why we mod the power with (m-1) :

This is a very neat proof.

Please upvote if I helped so that I can qualify to upvote others. :))

1 Like
11

Hello everyone Refer my answer for query about \mod{p-1}

#link: NMNMX whats wrong - #4 by l_returns - general - CodeChef Discuss
Feel free to ask queries :smiley:

12

Some good discussion also happened here- https://discuss.codechef.com/questions/131430/july-18-problem-discussion?sort=votes&page=1

Do have a look :slight_smile:

1 Like
13

You’re counting some cases more than once. Say, i is 5 and k is 4. You pick index 3 in your ‘pick a smaller number’ part and pick index 2 (there is only one number left to pick) in your (n-3, k-3) part. But that case is counted again when you pick index 2 in your ‘pick a smaller number’ part and index 3 for the (n-3,k-3) part.

I’m not 100% sure though. Try to calculate some values and see if they’re greater than expected.

14

Answer my question instead, please.

15

this link gives answer to your question only… I commented for only u but thought someone else also get the same doubt…

16

Since a^{p-1}=a^0 \mod p we can say that a^{x-k \cdot (p-1)}=a^x \mod p. If we take k = \left\lfloor\dfrac x {p-1} \right\rfloor, we will get mentioned equation.

17

Thanks to both. A little query, why can’t I add comment to any other answer except this one?

18

you need to have 50 reputation points for that. Currently you have 13.

19

Refer “new karma system” blog on discuss… For knowing minimum reputation to do stuff…

20

https://discuss.codechef.com/questions/68246/karma-on-codechef

21

Yes I gave same answer

22

This is the euler totient function
For prime numbers it is (p - 1). for the rest
https://en.wikipedia.org/wiki/Euler’s_totient_function#Computing_Euler’s_totient_function

23

thanks till now the clearest explanation.

1 Like
24

Thanks bro.

1 Like
25

Try 3-tower coloring question of hackerrank and read its editorial.

1 Like
26

@vijju123: Thank you. That explanation was very helpful.

27

@ritam777
During the contest, I was trying to do this but could not. Thank you so much as I now understand it :))

Sorry I am not qualifed to upvote otherwise I would have.

28

Why do subset or subsequence doesn’t matter?