Problem link : CodeChef: Practical coding for everyone
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?