Search code examples
c++modularexponentiation

Expression involving modular exponentiations in C++

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

Solution

  • 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;