51Nod 1130 N的阶乘的长度 V2(斯特林近似) 【数学】【斯特林公式】

发表于 | 更新于 | 分类于

在进入正试讲解之前我们先来看一道简单点的题目压压惊。

题目链接：51nod 1058

Description：
输入N求N的阶乘的10进制表示的长度。例如$6! = 720$，长度为3。

Input
输入N($1$ <= $N$ <= $10^6$)

Output
输出N的阶乘的长度

Input示例
6

Output示例
3

题目大意：
很明确，就是求n！的长度

解题思路：
我们知道，对于任意的数n，$len = log10(X) + 1$就是X这个数的长度。当N的值不超过10^6时，直接求的话N的阶乘长度$len = log10(1 \times 2 \times 3 \times 4 \times \ldots \times N) + 1$

$= log10(1) + log10(2) + log10(3) + log10(4) + …… + log10(N) + 1 $。这样实现看起来有点笨拙，不过是可以AC的。

Mycode:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1005;

int main()
{
    int n;
    cin >> n;
    double ans = 1;
    for(int i = 1; i <= n; ++i)
    {
        ans += (log10(i));
    }
    cout << (int)ans << endl;
    return 0;
}

而对于下面这道题目来说，因为数据范围变大了很多，所以需要考虑用更优的解法了。

题目链接：51nod 1130

Description：
输入N求N的阶乘的10进制表示的长度。例如$6! = 720​$，长度为3。

Input
第1行：一个数T，表示后面用作输入测试的数的数量。（$1 <= T <= 1000$)
第2 - T + 1行：每行1个数N。（$1 <= N <= 10^9$)

Output
共T行，输出对应的阶乘的长度。

Input示例
3
4
5
6

Output示例
2
3
3

题目大意：
和上道题一样，就是求$n!$的长度，不过数据范围大了很多。

解题思路：
有个叫作斯特林公式的神奇公式(可参考百度百科：斯特林公式)，可以利用它进行求解。注意，当$n=1$的时候，上面的公式不适用，所以要单独处理n=1的情况。

这种方法速度很快就可以得到结果。用它来求n!的位数就很easy了。

Mycode:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1005;
const double PI = acos(-1.0);
const double EXP = 2.718281828459;
int main()
{
    int T;
    long long n, ans;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld",&n);
        if(n == 1)
        {
            puts("1");
            continue;
        }
        ans = 0.5*log10(2*PI*n) + n*log10(n*1.0/EXP) + 1;
        cout << ans << endl;
    }
    return 0;
}
Donate comment here
0%