ALGORITHM

[$u!fur]

hi all. ..i know how to calculate the sum of divisors of a number as
well know how to calculate a^b mod n;
but here question is to calculate S % mod n where S = is the sum of
divisors of a ^ b.

a and b are very large...but can fit in int range..but its
multiplication can not fit...

give me a nice algo..i m stuck frm past 6 hrs...!!!

[Victor Bazarov]

$u!fur wrote:
> hi all. ..i know how to calculate the sum of divisors of a number as
> well know how to calculate a^b mod n;
> but here question is to calculate S % mod n where S = is the sum of
> divisors of a ^ b.

What's the meaning of ^ in your description? In C++ it means exclusive
OR. Also, what's "% mod"? In C++ % means remainder from division.

> a and b are very large...but can fit in int range..but its
> multiplication can not fit...
>
> give me a nice algo..i m stuck frm past 6 hrs...!!!

You got a C++ language question? For general algorithm help, try
'comp.programming'.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[$u!fur]

^ is power like 2 ^ 3 = 8 and my mistake "% mod " should be only %

[red floyd]

You can find a good hint here:

http://www.parashift.com/c++-faq-lite/how-to-post.html#faq-5.2

[gw7...@aol.com]

Are you allowed to work out the prime factorisation of a? If, for
example, a = p1 ^ a1 * p2 ^ a2 * p3 ^ a3, where p1, p2 and p3 are
prime (and ^ means "to the power of", which is not what it means in C+
+) then this would mean that all the divisors of a are:

p1 ^ x1 * p2 ^ x2 * p3 ^ x3 for 0 <= x1 <= a1 etc

which means all the divisors of a^b are:

p1 ^ x1 * p2 ^ x2 * p3 ^ x3 for 0 <= x1 <= b*a1 etc

so they all add up to something like:

(p1 ^ (a1 * b - 1)) / (p1 - 1) * same thing for p2, p3

(Note - unchecked, could be wrong in some detail)

which you might be able to calculate directly.

Hope that helps.
Paul.