如何高效使用Modulo？

Question

我正在做一项（对我自己而言）非常复杂的任务，我必须在给定 n 个片段的情况下计算最大可能的序列数。

我发现加泰罗尼亚数字代表这个序列，并且我让它适用于 n<=32。我得到的结果应该是mod 1.000.000.007。我遇到的问题是 "q" 和 "p" 对于 long long int 变得很大，我不能只 mod 1.000.000.007 在除以 "q" 和 "p" 因为我会得到不同的结果。

我的问题是，是否有真正有效的方法来解决我的问题，或者我是否必须考虑以不同方式存储值？我的限制如下： - 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);
}

Answer 1

如果您使用的是 gcc 或 clang 和 64 位目标，则存在 __int128 type。这为您提供了额外的工作空间，但显然只是在一定程度上。

很可能处理此类问题的最简单方法是使用 "bignum" 库，即处理任意大数的表示和算术的库。可以说最流行的开源示例是 libgmp - 你应该能够很容易地使用它来运行你的算法。它还针对高性能标准进行了调整。

显然，您可以自己重新实现这一点，例如将您的数字表示为一定大小的整数数组。您必须自己实现用于执行基本算术运算的算法，例如 +、-、*、/、%。如果您想将此作为一种学习体验，那很好，但是如果您只想专注于您要实现的算法，那么使用 libgmp 也没什么可耻的。

Answer 2

为了有效地解决这个问题，您需要使用 modular arithmetic, with modular inverses 代替除法。

很容易证明，在没有溢出的情况下，(a * b) % c == ((a % c) * b) % c。如果我们只是乘法，我们可以在每一步都得到结果 mod 1000000007 并且始终保持在 64 位整数的范围内。问题是分裂。 (a / b) % c 不一定等于 ((a % c) / b) % c.

为了解决除法问题，我们使用 modular inverses。对于具有 c 素数和 a % c != 0 的整数 a 和 c，我们总能找到满足 a * b % c == 1 的整数 b。这意味着我们可以将乘法用作除法。对于任何可被 a、(d * b) % c == (d / a) % c 整除的整数 d。这意味着 ((d % c) * b) % c == (d / a) % c，因此我们可以减少中间结果 mod c 而不会搞砸我们的除法能力。

我们要计算的数字的形式是(x1 * x2 * x3 * ...) / (y1 * y2 * y3 * ...) % 1000000007。我们可以改为计算 x = x1 % 1000000007 * x2 % 1000000007 * x3 % 1000000007 ... 和 y = y1 % 1000000007 * y2 % 1000000007 * y3 % 1000000007 ...，然后使用 extended Euclidean algorithm 和 return 计算 y 的 modular 逆 z (x * z) % 1000000007.

如何高效使用Modulo？

How to use Modulo efficiently?

c

performance

store

division

modulo