如何有效地使用取模运算？

Question

我正在进行一个（对我来说非常复杂的）任务，需要计算给定n个线段时可能的最大序列数。

我发现该序列可由Catalan数表示，并且我已经成功地将其用于n≤32。我得到的结果应该模1.000.000.007计算。我的问题是，“q”和“p”对于长长的整数来说太大了，我不能在除以“q”和“p”之前就对1.000.000.007取模，因为这会得到不同的结果。

我的问题是，是否有一种非常有效的方法来解决我的问题，还是我必须考虑以不同的方式存储这些值？

我的限制如下： - 仅使用stdio.h/iostream - 仅使用整数 - n ≤ 20,000,000 - n ≥ 2

#include <stdio.h>

long long cat(long long  l, long long  m, long long  n);

int main(){
    long long  n = 0;
    long long  val;
    scanf("%lld", &n);

    val = cat(1, 1, n / 2);

    printf("%lld", (val));

    return 0;
}

long long  cat(long long  q, long long  p, long long  n){
    if (n == 0) {
        return (q / p) % 1000000007;
    }
    else {
        q *= 4 * n - 2;
    }

    p *= (n + 1);

    return cat(q, p, n - 1);
}

- jHN

Answer 1

为了高效地解决这个问题，您需要使用模运算，其中模逆元替换除法。

简单地证明，在没有溢出的情况下，(a * b) % c == ((a % c) * b) % c。如果我们只是进行乘法，我们可以在每一步上对结果取模1000000007并始终保持在64位整数的范围内。问题在于除法。(a / b) % c不一定等于((a % c) / b) % c。

为了解决除法问题，我们使用模反元素。对于整数 a 和 c，其中 c 是质数且 a % c != 0，我们总是可以找到一个整数 b，使得 a * b % c == 1。这意味着我们可以使用乘法作为除法。对于任何可被 a 整除的整数 d，(d * b) % c == (d / a) % c。这意味着 ((d % c) * b) % c == (d / a) % c，因此我们可以将中间结果模 c 减小而不会影响我们进行除法运算的能力。

我们要计算的数字形式为(x1 * x2 * x3 * ...) / (y1 * y2 * y3 * ...) % 1000000007。相反，我们可以计算x = x1 % 1000000007 * x2 % 1000000007 * x3 % 1000000007 ...和y = y1 % 1000000007 * y2 % 1000000007 * y3 % 1000000007 ...，然后使用扩展欧几里得算法计算y的模逆z，并返回(x * z) % 1000000007。

- user2357112

---

这正是我正在寻找的。谢谢。 - jHN

Answer 2

如果您正在使用gcc或clang和64位目标，则存在 __int128类型。这为您提供了额外的位数，但显然只能到一定程度。

最简单的处理此类问题的方法可能是使用“bignum”库，即一个处理任意大的数字表示和算术的库。可能最受欢迎的开源示例是 libgmp - 您应该可以很容易地使用它来完成算法。它还调整了高性能标准。

当然，您也可以自己重新实现此功能，例如将数字表示为特定大小的整数数组。您必须自己实现执行基本算术（例如+，-，*，/，％）的算法。如果您想将其作为学习经验来进行操作，那么这样做就没有问题，但如果您只想专注于要实现的算法，使用libgmp也没有什么可耻的。

- pmdj