Innerve's summer code challenge, need help for SEQUA

Problem link : https://www.codechef.com/ISCC2017/problems/SEQUA

Can anyone help me for the above question, i am currently stuck up here.

So basically we need to find 1^1 + 2^2 + 3^3 + … + N^N mod M.

Hence, if N <= 1000 , Then i just did a brute force.

but if N > 1000, Then i observed that there will be a series of repetition, lets take it with an example.

Suppose N = 16, M = 4

0 1 2 3 == (0^0 + 1^1 + 2^2 + 3^3) == (0^0 + 1^1 + 2^2 + 3^3)

4 5 6 7 == ((4%4)^4 + (5%4)^5 + (6%4)^6 + (7%4)^7) == (0^4 + 1^5 + 2^6 + 3^7)

8 9 10 11 == ((8%4)^8 + (9%4)^9 + (10%4)^10 + (11%4)^11) == (0^8 + 1^9 + 2^10 + 3^11)

12 13 14 15 == ((12%4)^12 + (13%4)^5 + (14%4)^6 + (15%4)^7) == (0^12 + 1^13 + 2^14 + 3^15)

16 == (16%4)^12 == (0^16)

Hence i reduced this to calculating sum of gp mod M.

But i could not further proceed for this question, can some one help me out please?

It’s written here by liaojh:

link

Hope this helps~! =3

1 Like
//