c++ - C++ 中大型模的模幂运算失败

Question

这是我用来计算 (n^p)%mod 的代码。不幸的是，当我从 main() 方法调用它时，它会因 mod 的大值(在我的例子中是 mod = 10000000000ULL)而失败。任何的想法;为什么？

ull powMod(ull n, ull p, ull mod) {
    ull ans = 1;
    n = n%mod;
    while(p) {
        if(p%2 == 1) {
            ans = (ans*n)%mod;
        }
        n = (n*n)%mod;
        p /= 2;
    }
    return ans;
}

这里，ull 是 unsigned long long 的类型定义。

Answer 1

是的，您可以在 C++ 中完成。正如其他人所指出的那样，您不能直接这样做。使用少量数论知识，可以将问题分解为两个可管理的子问题。

首先考虑 10^10 = 2^10 * 5^10。这两个因素互质，因此您可以使用 Chinese remainder theorem使用幂模 2^10 和模 5^10 求幂模 10^10。

请注意，在下面的代码中，magic 值 u2 和 u5 是使用 Extended Euclidean Algorithm 找到的.您不需要自己编写此算法，因为这些值是常量。我用 maxima及其 gcdex函数，计算它们。

修改后的版本:

typedef unsigned long long ull;

ull const M  = 10000000000ull;

ull pow_mod10_10(ull n, ull p) {
  ull const m2 = 1024;    // 2^10
  ull const m5 = 9765625; // 5^10
  ull const M2 = 9765625; // 5^10 = M / m2
  ull const M5 = 1024;    // 2^10 = M / m5
  ull const u2 = 841;     // u2*M2 = 1 mod m2
  ull const u5 = 1745224; // u5*M5 = 1 mod m5

  ull b2 = 1;
  ull b5 = 1;
  ull n2 = n % m2;
  ull n5 = n % m5;

  while(p) {
    if(p%2 == 1) {
      b2 = (b2*n2)%m2;
      b5 = (b5*n5)%m5;
    }
    n2 = (n2*n2)%m2;
    n5 = (n5*n5)%m5;
    p /= 2;
  }

  ull np = (((b2*u2)%M)*M2)%M;
  np    += (((b5*u5)%M)*M5)%M;
  np    %= M;
  return np;
}