C++ 中大型 mod 的模取幂失败

Question

这是我用于计算的代码(n^p)%mod。不幸的是，当我从方法调用它时，它对于mod（在我的情况下mod = 10000000000ULL）的大值失败main()。任何的想法; 为什么？

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是一个 typedef unsigned long long。

Answer 1

是的，你可以在 C++ 中做到这一点。正如其他人指出的那样，你不能直接做到这一点。使用一点数论，可以将问题分解为两个可管理的子问题。

首先考虑一下10^10 = 2^10 * 5^10。这两个因子都是互质的，因此您可以使用中国剩余定理10^10通过幂 modulo2^10和 modulo找到幂模5^10。

请注意，在以下代码中，魔术值u2和u5是使用扩展欧几里得算法找到的。您不需要自己编写这个算法，因为这些值是常数。我使用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;
}