大数阶因数模数大素数

Question

我需要计算一个大数的阶乘(<= 1.000.000),我需要结果模数1000000007.我写了以下内容,但它在运行时生成错误(test.exe已停止工作).它仅适用于小数字.

long long unsigned modulo(long long unsigned nr){
    return nr % 1000000007;
}

long long unsigned fact(long long unsigned nr){
    if(nr)return modulo(nr * fact(nr - 1));
    else return 1;
}

更新1:

long long unsigned fact(long long unsigned nr){
    long long unsigned r = nr;
    while(--nr){
        r = modulo(r * nr);
    }
    return r;
}

Answer 1

这是因为您的实现使用递归.对于小数字,它工作正常,但对于大数字,它溢出堆栈.

这条线

if(nr)return modulo(nr * fact(nr - 1));

创建nr堆栈帧.由于堆栈空间非常有限,因此输入大量数据会导致堆栈溢出.

更改您的实现以使用factorial的迭代计算来避免崩溃.

完成崩溃后,处理数字溢出.不是在计算阶乘之后计算模数,而是在计算的每个步骤中继续应用模数.