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...!!!

 

[$u!fur]

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



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

V

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

 

[red floyd]

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...!!!

You can find a good hint here:

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

 

[gw7rib]

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...!!!

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.