代码之家 › 专栏 › 技术社区 › coder3101

为什么这个模块化的GCD在大输入端失败?

modular-arithmetic algorithm c++

coder3101 · 技术社区 · 6 年前

这个问题实际上来自一个名为codechef的竞争性编程网站。

问题如下。

给定整数A,B和N,您应该计算A^N+B^N和数字可能非常大,将其计算为1000000007(109+7)的模。

完整的问题是 here

对值的限制如下:

1<=A,B,N<=1e9(子任务1)

1<=A、B、N<=1e12(子任务#2)

B<=始终为A

我的解决方案通过第一个子任务,但当A、B、N的值非常大时,第二个子任务失败。

#include <bitset>
#include <iostream>

using std::bitset;
using std::cin;
using std::cout;

typedef unsigned long long ull;
constexpr size_t bit_size = sizeof(ull) * 8;

ull modular_exponetiation(ull a, bitset<bit_size> n, ull mod) {
  ull c = 0;
  ull d = 1;
  for (int t = n.size() - 1; t >= 0; t--) {
    c *= 2;
    d = ((d % mod) * (d % mod)) % mod;  //(d*d)%mod
    if (n[t] == 1) {
      c++;
      d = ((d % mod) * (a % mod)) % mod;  //(d*a)%mod
    }
  }
  return d;
}

ull euclid_gcd(ull a, ull b) {
  if (b == 0)
    return a;
  else
    return euclid_gcd(b, a % b);
}

int main() {
  int test;
  cin >> test;
  while (test--) {
    ull a, b, n;
    cin >> a >> b >> n;
    ull modder = a - b;
    if (modder != 0) {
      ull out_res = 0;
      bitset<bit_size> bin_rip(n);
      ull first_mod_res = (modular_exponetiation(a, bin_rip, modder) +
                           modular_exponetiation(b, bin_rip, modder)) %
                          modder;
      if (first_mod_res == 0)
        out_res = modder;
      else
        out_res = euclid_gcd(modder, first_mod_res);
      cout << out_res % 1000000007 << std::endl;
    } else {
      // mod by 0 is not defined using the problem defined result.
      // GCD(0,a) == a;
      ull modder = 1000000007;
      bitset<bit_size> bin_rip(n);
      ull res = (modular_exponetiation(a, bin_rip, modder) +
                 modular_exponetiation(b, bin_rip, modder)) %
                modder;
      cout << res << std::endl;
    }
  }
  return 0;
}

请求

这不是一个家庭作业,也不是我想要一个精确的答案或代码更正。我确实理解所有这些,但不明白为什么它会在更大的价值观上失败?

2 回复 | 直到 6 年前

GolamMazid Sajib 6 年前

如果 modder =1e12则模块不工作。因为1e12*1e12。会有溢出。

this 无溢出的模。

你可以试试这个。这里乘法是求和的。

long long multiply(long long a,long long b,long long m){
if(b == 0){
    return 0;
}
if(b==1){
    return a%m;
}
if(b&1){
    return ((a%m)+multiply(a,b-1,m))%m;
}
long long x = multiply(a,b>>1,m);
return multiply(x,2,m);
}

long long bigmod(long long a,long long b, long long m){
if(b == 0){
    return 1;
}
if(b == 1){
    return a%m;
}
if(b & 1){
    return multiply(a%m,bigmod(a,b-1,m),m);
}
long long x = bigmod(a,b>>1,m);
return multiply(x,x,m);
}

coder3101 6 年前

因为他指出了问题。

为了更好的理解,我将亲自回答。

d = ((d % mod) * (d % mod)) % mod; 
d = ((d % mod) * (a % mod)) % mod;

是两条断开并导致溢出的线。所有学分都归@sajib。

所以我在这里详细解释。

(a * b) % m

如果两者都发生,将导致溢出 a 和 b 都是非常大的长值。

天真的做法

有效解决方案 :因为a和b可能是非常大的数字,如果我们尝试直接乘法,那么它肯定会溢出。因此我们使用乘法的基本方法,即。,

a * b = a + a + â¦ + a (b times)

计算中溢出。但是,如果我们试图增加一个重复的B值,那么它肯定会超时B的大值,因为这种方法的时间复杂度将变成O(B)。

所以我们把上面重复的步骤 一

If b is even then 
  a * b = 2 * a * (b / 2), 
otherwise 
  a * b = a + a * (b - 1)

具体实施如下:

// Returns (a * b) % mod
long long moduloMultiplication(long long a,
                               long long b,
                               long long mod)
{
    long long res = 0;  // Initialize result

    // Update a if it is more than
    // or equal to mod
    a %= mod;

    while (b)
    {
        // If b is odd, add a with result
        if (b & 1)
            res = (res + a) % mod;

        // Here we assume that doing 2*a
        // doesn't cause overflow
        a = (2 * a) % mod;

        b >>= 1;  // b = b / 2
    }

    return res;
}