阶乘位数—Big Number

超、凢脫俗 2022-06-12 06:16 149阅读 0赞

Big Number  
In many applications very large integers numbers are required. Some of these applications are using keys for secure transmission of data, encryption, etc. In this problem you are given a number, you have to determine the number of digits in the factorial of the number.  
Input  
Input consists of several lines of integer numbers. The first line contains an integer n, which is the number of cases to be tested, followed by n lines, one integer 1 ≤ n ≤ 10 7 on each line.  
Output  
The output contains the number of digits in the factorial of the integers appearing in the input.  
Sample Input  
2  
10  
20  
Sample Output  
7  
19  
翻译起来大体意思就是：  
在许多应用中，需要非常大的整数。 这些应用程序中的一些正在使用密钥来进行数据的安全传输，加密等。在这个问题中，您将得到一个数字，您必须确定数字的乘积中的位数。  
输入  
输入由几行整数组成。 第一行包含一个整数n，它是要测试的情况数，后面是n行，每行一个整数1≤n≤107。  
产量  
输出包含出现在输入中的整数的阶乘数。  
样品输入  
2  
10  
20  
样品输出  
7  
19

题解：整体就是运用就是斯特林公式。因为斯特林公式是求解n！的近似公式，而本题只需要求解有多少位。底层数学原理就是求一个数n的数位可以使用 digits = log10(n)。然后利用斯特林公式求出n！的近似值就可以利用log10来求得数位了。  
斯特林公式（Stirling’s approximation）是一条用来取n的阶乘的近似值的数学公式。一般来说，当n很大的时候，n阶乘的计算量十分大，所以斯特林公式十分好用，而且，即使在n很小的时候，斯特林公式的取值已经十分准确。  
利用斯特林（Stirling）公式的进行求解。下面是推导得到的公式：　res=(long)( (log10(sqrt(4.0\*acos(0.0)*n)) + n*(log10(n)-log10(exp(1.0)))) + 1 );  
当n=1的时候，上面的公式不适用，所以要单独处理n=1的情况！  
这种方法速度很快就可以得到结果。

#include <stdio.h>
    #include <math.h>
    const double PI = 3.14159265358979323846f;
    
    inline int getDigits(int n)
    {
        double num = double(n);
        int ans = (int)(0.5*log10(2.0*PI*num) + num*(log(num)-1)/log(10.0)) + 1;
        return ans;
    }
    
    int main()
    {
        int T, n;
        scanf("%d", &T);
        while (T--)
        {
            scanf("%d", &n);
            printf("%d\n", getDigits(n));
        }
        return 0;
    }