2

我已经开始做有竞争力的编程，大多数时候我发现数字的输入大小就像

     1 <= n <=  10^(500).

所以我知道这就像 500 位数字，不能存储在简单的 int 内存中。我知道c和c++。

我想我应该使用一个数组。但后来我对如何找到

   if ( (nCr % P) == 0 )  //for all (0<=r<=n)//

我认为我会将它存储在一个数组中，然后找到 nCr。这需要对数字进行乘法和除法编码，但是模数呢。

还有其他方法吗？

谢谢。

4

4 回答 4

3

我认为您不想自己编写乘法和除法代码，而是使用 GNU MP Bignum 库http://gmplib.org/之类的东西

于 2012-09-06T06:19:29.567 回答
1

如果我们必须计算 nCr mod p（其中 p 是素数），我们可以计算阶乘 mod p，然后使用模逆来找到 nCr mod p。如果我们必须找到 nCr mod m（其中 m 不是素数），我们可以将 m 分解为素数，然后使用中国剩余定理 (CRT) 找到 nCr mod m。

#include<iostream>
using namespace std;
#include<vector>

/* This function calculates (a^b)%MOD */
long long pow(int a, int b, int MOD)
{
    long long x=1,y=a; 
    while(b > 0)
    {
        if(b%2 == 1)
        {
            x=(x*y);
            if(x>MOD) x%=MOD;
        }
        y = (y*y);
        if(y>MOD) y%=MOD; 
        b /= 2;
    }
    return x;
}

/*  Modular Multiplicative Inverse
    Using Euler's Theorem
    a^(phi(m)) = 1 (mod m)
    a^(-1) = a^(m-2) (mod m) */
long long InverseEuler(int n, int MOD)
{
    return pow(n,MOD-2,MOD);
}

long long C(int n, int r, int MOD)
{
    vector<long long> f(n + 1,1);
    for (int i=2; i<=n;i++)
        f[i]= (f[i-1]*i) % MOD;
    return (f[n]*((InverseEuler(f[r], MOD) * InverseEuler(f[n-r], MOD)) % MOD)) % MOD;
}

int main()
{    
    int n,r,p;
    while (~scanf("%d%d%d",&n,&r,&p))
    {
        printf("%lld\n",C(n,r,p));
    }
}

在这里，我使用 long long int 来表示数字。

于 2014-05-31T09:11:49.233 回答
1

关于大量库，我使用了 ttmath，它提供了任意长度的整数、浮点数等，以及一些非常好的操作，而且体积相对较小。

但是，如果您只是想弄清楚 (n^e) mod m 是什么，即使没有非常大的数字计算，您也可以对非常大的 e 值执行此操作。下面是我添加到本地 ttmath 库中的一个函数：

/*!
        mod power this = (this ^ pow) % m
        binary algorithm (r-to-l)

        return values:
        0 - ok
        1 - carry
        2 - incorrect argument (0^0)
    */
    uint PowMod(UInt<value_size> pow, UInt<value_size> mod)
    {
        if(pow.IsZero() && IsZero())
        // we don't define zero^zero
        return 2;

        UInt<value_size> remainder;
        UInt<value_size> x = 1;

        uint c = 0;

        while (pow != 0)
        {
            remainder = (pow & 1 == 1);
            pow /= 2;
            if (remainder != 0)
            {
                c += x.Mul(*this);
                x = x % mod;                                
            }

            c += Mul(*this);
            *this = *this % mod;        
        }

        *this = x;
        return (c==0)? 0 : 1;
    }

我不相信你需要为这个算法存储一个大于 n^2 的数字。如果您不想使用这些标头，应该很容易修改它以删除与 ttmath 相关的方面。

如果您关心的话，您可以通过查找模幂运算在线找到数学的详细信息。

于 2012-09-06T06:30:15.667 回答
0

在许多。在这些编码比赛中，很多情况下，你的想法是你实际上并不计算这些大数字，而是在不计算的情况下弄清楚如何回答问题。例如：

What are the last ten digits of 1,000,000! (factorial)?

这是一个超过五百万位的数字。但是，我可以不用电脑来回答这个问题，甚至不用笔和纸。或者问一个问题：什么是 (2014^2014) 模 153？这是在 C 中计算的一种简单方法：

int modulo = 1;
for (int i = 0; i < 2014; ++i) modulo = (modulo * 2014) % 153;

同样，您避免使用 6,000 位数字进行计算。（你实际上可以更快地做到这一点，但我不是想参加比赛）。

于 2014-05-31T09:29:56.683 回答