UVA1185 【Big Number】

第一次写一篇黑题的题解!!内心充满激动!

首先简述一下蒟蒻做这道题的过程:

这道题要求我们求\(n!\)的位数,所以蒟蒻首先打一个小小的表:

\(1, 1, 1,2, 3, 3, 4 ,5, 6, 7, 8……\)

貌似没有什么规律可找\(……\)

于是蒟蒻无耻地上了\(OEIS\)找了一下,发现了这么几个递推式:

\(1·\quad a(n) = floor(log(n!)/log(10)) + 1\)

这个式子要用到\(n!\),所以显然不可用,看下一个。

$2·\quad a(n) = A027869(n) + A079680(n) + A079714(n) + A079684(n) + A079688(n) + A079690(n) + $
\(\quad \quad \quad \quad \quad A079691(n) + A079692(n) + A079693(n) + A079694(n);\)

解释一下,后面九个数列分别为\(n!\)中数字\(1\sim9\)出现的个数,显然这个公式也不太可用,看下一个。

\(3·\quad a(n) = A055642(A000142(n)).\)

这个式子中,外层为求\(n\)的位数,内层就是阶乘,所以显然也不可用。

\(4·\quad a(n) = ceiling(log10(1) + log10(2) + ... + log10(n))\)

等等!!这个式子貌似是\(O(n)\)的!!

于是,我们就愉快地\(A\)掉了此题。


但学习需要严谨的态度,所以我们来证明一下这个\(O(n)\)的式子:

首先,感谢这篇博客提供证明思路。

\(P.s.:\)以下推导过程均默认\(log\)的底数为\(10\)。

对于一个正整数\(n\),对于它有\(10^{x-1}\leq n<10^x\),那么显然\(n\)有\(x\)位。继续向下推导:

\[log(10^{x-1})\leq log(n)<log(10^x)\]

\[x-1\leq log(n)<x\]

由于\(c++\)默认向下取整,所以\(log(n)=x-1\),所以\(n\)的位数\(=log(n)+1\).

所以,我们得出答案式子为\(:\)

\[ans=log(n!)+1\]

\[\quad\quad\quad\quad\quad\quad\quad\quad\quad\ =log(1 * 2 * 3 * …… * n) + 1\]

\[\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad=log(1)+log(2)+……+log(n)+1\]

\[\quad\quad\quad= \sum_{i =1}^nlog(i)+1\]

证毕。

所以,我们预处理出\(log\)的前缀和,向上取整即可。

code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define int long long

int n, temp;
double lg[10000001];

signed main() {
    scanf("%lld", &n);
    for (int i = 1; i <= 10000001; i++)
        lg[i] = lg[i - 1] + log10(i);
    while (n--) {
        scanf("%lld", &temp);
        printf("%lld\n", (long long)lg[temp] + 1);
    }
    return 0;
}

完结撒花(✪ω✪)

上一篇:Allegro 16.6快捷键设置


下一篇:使用scipy.integrate.quad执行3D积分