模块化算术的优化代码

我正在尝试计算大数的下面的表达式。模块化算术的优化代码

N!/((N/2)!(N/2)!)

由于该表达式的值将是非常大的，我只需要这个表达式的值模量的一些素数。假设这个表达式的值是x，我选择素数1000000007;我在寻找x % 1000000007。

这是我的代码。

#include<iostream> 
#define MOD 1000000007 
using namespace std; 
int main() 
{ 
    unsigned long long A[1001]; 
    A[2]=2; 
    for(int i=4;i<=1000;i+=2) 
    { 
     A[i]=((4*A[i-2])/i)%MOD; 
     A[i]=(A[i]*(i-1))%MOD; 

    while(1) 
    { 
     int N; 
     cin>>N; 
     cout<<A[N]; 
    } 
}

但是，即使这么多的优化失败了N的大值。例如，如果N是50，正确的输出是605552882，但是这给了我132924730。如何进一步优化以获得正确的输出？

注意：我只考虑N为偶数。

来源

2013-02-06 g4ur4v

按答案它看起来像有没有什么可以做，以提高该code.I'll尝试使用一些其他的公式来代替。 – g4ur4v

[快速计算n！的方法！ mod m其中m是素数？]（http://stackoverflow.com/questions/9727962/fast-way-to-calculate-n-mod-m-where-m-is-prime）。此外，这是一个更好的适合，但没有答案：[如何计算nCk％P的大素数和非常大的N？]（http://stackoverflow.com/questions/14475139） –

当您进行模块化算术时，不存在除法之类的操作。相反，你采用分母的模逆，并乘。模逆计算使用在1779年扩展欧几里德算法，通过艾蒂安·贝祖发现：

# return y such that x * y == 1 (mod m) 
function inverse(x, m) 
    a, b, u := 0, m, 1 
    while x > 0 
     q, r := divide(b, x) 
     x, a, b, u := b % x, u, x, a - q * u 
    if b == 1 return a % m 
    error "must be coprime"

的divide函数返回二者商和余数。上面给出的所有赋值运算符都是同时赋值，其中首先计算右边的所有值，然后同时赋值所有的左边值。你可以在my blog看到更多关于模块算术的知识。

来源

2013-02-06 19:13:28 user448810

对于初学者来说需要在所有无模除法，您的公式可以rewrited如下：（！（N/2）^ 2）

N/ =（1.2.3 .. （1.2.3 ... N/2）*（1.2.3 ... N/2）） =（（N/2 + 1）... N）/（1.2.3。 ...... N/2））
- 确定现在您正在由较小
- 除以更大号码，以便可以通过迭代除数multiplicating和红利
- 所以展台子的结果也有类似幅度
- 任何时候都数整除2将它们转移离开
- 这将确保不会溢出
- ，如果你是在和（N/2）！而不是继续仅用于其余部分。
- 任何时候都子结果是整除什么将它们划分
- ，直到你在这之后留下divison 1
- 你可以用模算术直到normaly年底繁殖。
查看更多高级方法。
- N！和（N/2）！可分解远远超出它似乎一见钟情
- 我已经解决了有一段时间了，...
- 这里是我发现：Fast exact bigint factorial
- 在快捷方式方面N！和（（N/2）！）^ 2将完全消失。
- 只有简单的素数分解+ 4N < - > 1N修正会提醒

解决方案：

I. (4N!)=((2N!)^2) . mul(i=all primes<=4N) of [i^sum(j=1,2,3,4,5,...4N>=i^j) of [(4N/(i^j))%2]] 
II. (4N)!/((4N/2)!^2) = (4N)!/((2N)!^2) 
---------------------------------------- 
I.=II. (4N)!/((2N)!^2)=mul(i=all primes<=4N) of [i^sum(j=1,2,3,4,5,...4N>=i^j) of [(4N/(i^j))%2]]

的唯一的事情就是N必须由4整除...因此在所有方面都是4N。
如果您有N％4！= 0比解决N-N％4和结果纠正由misin 1-3数字。

希望它有助于

来源

2013-09-03 14:31:39 Spektre

模块化算术的优化代码

回答

相关问题