0

hey guys,

i have a problem with this question..
Given n and m, calculate 1^1 + 2^2 + 3^3 + ... + n^n modulo m.

here i cant use power function directly as it only works for very very small inputs. Test your code on anything larger and you will get the wrong answer, since a double is not even precise enough to calculate the answer for n = 20, let alone n=10^18. (example: Math.pow(20,20) == Math.pow(20,20)+1.

what do i do now...

3
Contributors
3
Replies
4
Views
5 Years
Discussion Span
Last Post by StuXYZ
0

Not sure how much of the answer I should give. [if it is too much help then I am sorry]. If this insufficient, please reply and let us know.

The first thing to note is that any integer number x, can be expressed as:
[tex]x=a m + r[/tex] were a and r are integer and m is your modulo number.

Then note that [tex]x^2 = (am+r)*(am+r)=a^2m^2 + 2ar m + r^2[/tex] which clearly modulo
m is just r^2.

That should be enough for you to see how to proceed.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.