动力溢出

Question

如果我正在计算 [x*(a^b)%mod+y%mod]%mod，如果我只使用 (a^b)%mod，将其与 x 相乘会得到正确答案吗？逐步计算 (x*(a^b))%mod 不是更好的主意吗？只是想向自己证明为什么不包括 x 有效。可以做什么？

Answer 1

试试这个代码。这个想法是引入新的模块加法、乘法和求幂函数：

#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)));
    }
}

动力溢出

Overflow with power

c++

modulus

integer-overflow

exponent