c++ - 如何在 C++ 中查找大数模 1000000007 的阶乘？

Question

Find the factorial of large number modulo 1000000007

在 Python 或 Java 中，这没有问题，但在 C++ 中存在溢出约束。

这是我试过的代码:

#include<iostream>
 #define ull long long int
 #define mod 1000000007
 ull fact(ull n)
 {
           if(n==1 || n==0) return 1;
           return ((n%mod)*(fact(n-1)%mod)%mod);
 }
 int main()
 {
              cout<<fact(50000)<<endl;
              return 0;
 }

但输出无效。

Answer 1

检查此代码。应该没有任何问题，因为 unsigned long long 可以轻松存储任何模值 10^9+7。我的意思是，如果您使用的是模块化值(value)而不是实际值(value)，那您为什么还要关心它呢？ (众所周知，10^9+7 可以存储在 ull 中)。

 ull ans;
    ull fact(int n)
    {
        if(n<INT_MAX)
        {
        ans=1;
        for(int i=2;i<=n;i++)
         ans=(ans*i)%mod;
         return ans;
        }
    }

这将简单地进行阶乘。

这里使用了 n<INT_MAX 条件，因为如果我们不使用它，那么如果 n=INT_MAX for 循环的索引增量(i++)可能会导致 INT_MAX 的值增加，这将使它0. 所以条件永远不会为假，会陷入死循环。

注意:如果您想在 C++ 中精确计算阶乘，您可以采用 1000 个字符的数组，其中每个字符代表一个数字。然后你会逐渐乘以得到结果。 n*(n-1)*..2*1

注意:如果您正在进行多次递归调用，那么它可能会导致堆栈内存溢出，因为每个函数调用都会导致推送一个帧(包含它的返回点等)。