0

I am wanting to evaluate the expression, (an + bn + cn) % 1000000003 , in C++. I a getting overflow errors when n is very large. Can someone help me with this ? More specifically a = q + 1, b = - 2 * q and c = q - 1. I have been following the function outlined in this

Can I break (an + bn + cn) % 1000000003 into (an) % 1000000003 + (bn) % 100000003 + (cn) % 1000000003 or something similar ? Also I cannot use anything more than unsigned long long int

Community
  • 1
  • 1
Mayank Jha
  • 3
  • 3

1 Answers1

0

You can distribute your modulo. Mathematically, this will be sound:

( ((a^n)%1000000003) + ((b^n)%100000003) + ((c^n)%1000000003) ) % 1000000003;

This will prevent you from having to compute numbers that are out of bounds, allowing you to choose larger values for n.

Proof.

Just be sure to use pow in the math.h module:

( ((pow(a, n))%1000000003) 
    + ((pow(b, n))%100000003) 
    + ((pow(c, n))%1000000003) ) % 1000000003;
Bucket
  • 7,415
  • 9
  • 35
  • 45
  • but as you can see b is negative won't this cause erroneous results ? – Mayank Jha Oct 09 '13 at 16:06
  • See [this answer](http://stackoverflow.com/questions/12276675/modulus-with-negative-numbers-in-c). If you don't want negatives, handle them in your code! :) – Bucket Oct 09 '13 at 16:08
  • I dont think this would work if `n` is very large say 1000000000 – Mayank Jha Oct 09 '13 at 16:08
  • using `pow` can cause precision errors, I am using Modular Exponentiation. Will the identity you've written still work if I am applying modular exponentiation ? – Mayank Jha Oct 09 '13 at 16:15
  • Yes, it should still work with Modular Exponentiation. All this does is reduce the overhead on number storage size. – Bucket Oct 09 '13 at 19:53