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...
Jump to PostYou could use an arbitrarily large number library.
is there any method without using this library..
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.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.