please explain your approach? is there is any formulae? asked 27 Jul '17, 22:06

This problem was from a very old contest, you can see all sorts of solutions here. In fact, a lot of people copied the same solutions from that contest... Here's mine, which takes $O(M\times log(N))$ in runtime. My thought process went like this: First, realize that $x^p \equiv (x \bmod M)^p \bmod M$. This reduces $\displaystyle\sum_{c=0}^{N} c^c \bmod M$ for all $c > M$ to a geometric series sum where $c < M$, essentially: $\displaystyle\sum_{c=0}^{N} c^c \bmod M \equiv \displaystyle\sum_{c=0}^{M1} \displaystyle\sum_{k=0}^{\lfloor\frac{Nc}{M}\rfloor} c^{c + k M} \bmod M$, Which can be broken down into: $\displaystyle\sum_{c=0}^{M1} c^c \displaystyle\sum_{k=0}^{\lfloor\frac{Nc}{M}\rfloor} c^{k M} \bmod M$, As fast as that sounds, all that left right now is to calculate the geometric series sum $\displaystyle\sum_{k=0}^{\lfloor\frac{Nc}{M}\rfloor} c^{kM} \bmod M$, which can be reduced to the geometric series formula. However, because $M$ is not always coprime with the divisor, I cannot use the formula with Modular Multiplicative Inverse and Fermat's little theorem. I can, however, use matrix exponentiation to calculate the sum: $\begin{pmatrix}c^M & 1 \\ 0 & 1 \end{pmatrix} ^ {\lfloor\frac{Nc}{M}\rfloor} = \begin{pmatrix}c^{M {\lfloor\frac{Nc}{M}\rfloor}} & \displaystyle\sum_{k=0}^{{\lfloor\frac{Nc}{M}\rfloor}  1} c^{kM} \bmod M \\ 0 & 1 \end{pmatrix}$ Adding the 2 components on the first row gives the geometric series sum. This means I can apply fast exponentiation to the matrix exponentiation and that will calculate the sum in $O(log(\lfloor\frac{Nc}{M}\rfloor))$ time. In total, I took $M1$ iterations of $O(log(M) + log(\lfloor\frac{Nc}{M}\rfloor))$ to calculate $c^c$ and geometric series sum. And reducing the runtime estimation: $O(log(M) + log(\lfloor\frac{Nc}{M}\rfloor)) = O(log(M) + log(N)  log(M)) = O(log(N))$, Thus my runtime ended at $O(M\times log(N))$ and I am done. Quick note that for $c = 0$ only $0^0 = 1$, and all other $0^k = 0$, thus our actual answer will be: $\displaystyle\sum_{c=0}^{N} c^c \bmod M \equiv 1 + \displaystyle\sum_{c=1}^{M1} c^c \displaystyle\sum_{k=0}^{\lfloor\frac{Nc}{M}\rfloor} c^{k M} \bmod M$. For a detailed explanation, read below. answered 27 Jul '17, 23:09

the solution provided by 5 star guy @Mr is not the way an actual 2 or 3 star person can understand..its actually a high level..it shud hve broken down in steps in order to understand..just because u understand it doesn"t mean u can put it in same way to different person...basically less than 5 star people needs more explanation to understand the logics..try to provide better explanation dude..no hard feelings...cheers up! answered 29 Jul '17, 01:11
1
@liaojh uses standard mathematical notation and his approach is pretty clear. He has even provided a link to a tutorial for matrix exponentiation, which is the core algorithm he has used. Maybe you should actually put in some effort into understanding the solution.
(29 Jul '17, 01:43)

if(m<=n) e.g : (2^2+(m+2)^(m+2)+(m2+2)^(m2+2)+.....)mod(m)=2^2(1+2^m+2^2*m+....) which is a simple sum of GP.Do this for m number therfore O(m). else calculate trivialy 1^1+2^2+3^3+... therefore in worst case O(10^3) You probably know that one can calculate the power of a number in logarithmic time. You can also do so for calculating the sum of the geometric series. Since it holds that1 + a + a^2 + ... + a^(2*n+1) = (1 + a) * (1 + (a^2) + (a^2)^2 + ... + (a^2)^n), you can recursively calculate the geometric series on the right hand to get the result. This way you do not need division, so you can take the remainder of the sum (and of intermediate results) modulo any number you want. algo: geometricSeriesMod[a_, n_, m_] := Module[ {q = a, exp = n, factor = 1, sum = 0, temp}, While[And[exp > 0, q != 0], If[EvenQ[exp], temp = Mod[factorPowerMod[q, exp, m], m]; sum = Mod[sum + temp, m]; exp]; factor = Mod[Mod[1 + q, m]factor, m]; q = Mod[q*q, m]; exp = Floor[ exp /2]; ]; Return [Mod[sum + factor, m]] ] Parameters: a is the "ratio" of the series. It can be any integer (including zero and negative values). n is the highest exponent of the series. Allowed are integers >= 0. m is the integer modulus != 0 answered 28 Jul '17, 01:23
3
When copying an explanation from elsewhere you should at least give credit to the original writer. (Source)
(29 Jul '17, 01:58)
please explain in easy way for 23 star users.huh
(31 Jul '17, 09:09)
