Can somebody help me how to do this ?

[Spoiler]

I realized following, 1. As k <= 50, only last two digits of n matter, so just calculate (n ^ n)%100, which can be simplified as ((n%100) ^ (n%100)) % 100. 2. But you don't need to do this for all n, as there are only 100 possible values for n % 100. 3. This gives us ~53 numbers which can appear as the last two digits of n^n, and we can easily count how many numbers are there for each such number. The same last digits repeat every 100 numbers. 4. The remaining issue is how many ways can be combine these numbers to get a certain remainder. For example, if K = 3, we count do take any 3 numbers from those numbers who's square ends with 1. But I am not able to extend this to calculate all such combos.

I have the feeling that n power n modulo k is periodic in n, the period being a multiple of k, i.e. there exists M such that (n+Mk)^(n+Mk) = n^n modulo k. Using this fact, you can infer the distribution of n^n modulo k, without actually computing all the terms, then design an algorithm that's efficient even for a huge n (using careful combinatoric). But my math is too limited to prove the assertion and find M. A brute force approach is probably doable, as k is small (you search for a period that works for n < 10^5 and hope that it generalizes. But, frankly, I'm here to do programming, not math, so I won't pursue this route. Good luck to the braves!

Fun fact :
- it is estimated that there are 10^80 atoms in the universe.
- it is estimated that in 2018, there were around 10^22 bytes of data stored
- You can store the number N on around log2(N) bits

Biggest N to be tested is 10^400 ,so N^N is... (10^400)^(10^400). log2((10^400)^(10^400)) = log2(10) * 400^(10^400) >>>>>> 10^80 * 10^22.

If you planned to actually generate and store that number, I hope you do have a good memory : if every atom of the universe was the entire world's memory, you'd still run out of memory :)

And, in the same way :
There are 2^n-1 subsets of a set of length n.
So if you were to generate 2^(10^400) - 1 numbers... Well, same issue :)

What's the story with the name of this problem. I don't think it's number is 250 thousand 250 :]