c - 求两个非常大的数与非常大的数的乘积模

Question

在编程练习中，我需要找出一个非常大的数字的模数，例如 2 的幂 500000（输入中的最大数字），其中 1000000007 作为其他计算的一部分。

正如我可能不得不多次发现的那样，一种方法是创建一个包含 5,00,000 的数组。但它会阻塞大量内存，所以我想知道有没有更好的方法来做到这一点？

Answer 1

这是使用重复平方算法的绝佳时机。您可以按如下方式计算 x ^y (mod modulus)：

int repeatedSquaring(int x, int y, int modulus) {
    if (y == 0) return 1;
    int val = repeatedSquaring(x, y / 2);
    val = (val * val) % modulus;

    if (y % 2 == 1) {
        val = (val * x) % modulus;
    }

    return val;
}

该算法只需要 O(log y) 乘法和模数来计算。此外，每个中间值最多为modulus²，因此如果您的模数不是太大，您可以使用 plain ints 进行计算。

希望这可以帮助！

Answer 2

像这样简单的东西怎么样？：

#include <stdio.h>

unsigned long PowMod(unsigned long p)
{
  unsigned long prod;

  if (p == 0)
    return 1;
  if (p == 1)
    return 2;

  prod = PowMod(p / 2);
  prod = (unsigned long long)prod * prod % 1000000007ULL;
  if (p % 2 != 0)
  {
    prod = prod * 2 % 1000000007ULL;
  }

  return prod;
}

int main(void)
{
  printf("%lu\n", PowMod(3));
  printf("%lu\n", PowMod(4));
  printf("%lu\n", PowMod(30));
  printf("%lu\n", PowMod(31));
  printf("%lu\n", PowMod(32));
  printf("%lu\n", PowMod(33));
  return 0;
}

输出（ideone）：

8
16
73741817
147483634
294967268
589934536