优化模块化算法的代码

Question

我试图计算大数字的下面的表达式.

由于这个表达式的值会非常大,我只需要这个表达式的值为一些素数.假设这个表达式的值是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为偶数.

Answer 1

进行模运算时,不存在除法等操作.相反,你采用分母的模逆,并乘以.使用由Etienne Bezout在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函数返回商和余数.上面给出的所有赋值运算符都是同时赋值,其中首先计算所有右侧,然后同时分配所有左侧.你可以看到更多关于模算术在我的博客.