Overflow with power

Question

If I am calculating [x*(a^b)%mod+y%mod]%mod, if I just use (a^b)%mod, would multiplying that with x give me the correct answer? Wouldn't calculating (x*(a^b))%mod in steps be a better idea? Just trying to justify to myself why not including x works. What can be done?

Is `A[i]` integer? Note that `x * (2^y) == x << y` when `y` is a non-negative integer. — timrau, Jan 01 '16 at 13:15
Type casting the pow to long long. Yes A[i] is an integer, so I will use the left shift operator, but still won't an integer overflow happen? — someone1, Jan 01 '16 at 13:17
See this: http://stackoverflow.com/questions/8496182/calculating-powa-b-mod-n — kfx, Jan 01 '16 at 13:17
In general, you should never use the `pow` function when solving this kind of (competitive programming) questions. Read this: http://codeforces.com/blog/entry/21844 — kfx, Jan 01 '16 at 13:19
I have changed the code using binary operator then performing mod on the product, yet it gives wrong answer. — someone1, Jan 01 '16 at 13:22
The problem is that you need to take the remainder at each step of the exponentiation, not just at the end. See the first answer to my linked SO question for the algorithm you need to use instead of the `<<` operator. — kfx, Jan 01 '16 at 13:24
Sorry for the clutter, but is this okay? Updating in the original post too. — someone1, Jan 01 '16 at 13:28
Solved! Thank you so much! :D I still have one doubt though. If I am calculating [x*(a^b)%mod+y%mod]%mod, if I just use (a^b)%mod, would multiplying that with x give me the correct answer? Wouldn't calculating (x*(a^b))%mod in steps be a better idea? Just trying to justify to myself why not including x works. Thanks :D — someone1, Jan 01 '16 at 13:32
Also see: http://stackoverflow.com/questions/11272437/calculating-abmod — SamB, Jan 04 '16 at 22:51

kfx · Accepted Answer · 2016-01-01T13:42:51.893

1

Try this code. The idea is to introduces new functions for modular addition, multiplication, and exponentiation:

#define MOD 1000000007

inline int modadd(int a, int b) {
    return ((long long)a + b) % MOD;
}

inline int modmult(int a, int b) {
    return ((long long) a * b) % MOD;
}

inline unsigned modexp(unsigned base, unsigned exp)
{
  unsigned result = 1;
  while (exp > 0) {
      if (exp & 1) result = ((unsigned long long)result * base) % MOD;
      base = ((unsigned long long)base * base) % MOD;
      exp >>= 1;
  }
  return result;
}

int main(void)
{
    unsigned A[3] = {1, 2, 3};
    unsigned r[3];
    unsigned i, n = 3;

    r[0] = 0;
    r[1] = modmult(2, A[0]);
    for (i = 1; i < n; i++) {
        r[i+1] = modadd(r[i], modmult(A[i], modexp(2, i)));
    }
}

edited Jan 01 '16 at 13:42

answered Jan 01 '16 at 13:38

kfx

8,136
3
28
52

Hey thanks! I solved it using the modular exponentiation function! This is great too. Maybe if you could answer this doubt? I can't seem to understand this bit. If I am calculating [x*(a^b)%mod+y%mod]%mod, if I just use (a^b)%mod, would multiplying that with x give me the correct answer? Wouldn't calculating (x*(a^b))%mod in steps be a better idea? Just trying to justify to myself why not including x works. – someone1 Jan 01 '16 at 13:41
2

If `a^b` means "a to the power of b", then the problem is that both `x*(a^b)` might overflow integer range even if `a^b` does not overflow it. Either use `modmult(x, a^b)` or cast `x` to `long long`. – kfx Jan 01 '16 at 13:45

Overflow with power

1 Answers1