题目大意: 求十进制下 x! 的位数
这题其实就是要求 \(\lg\) 函数值的前缀和啊
对于一个数 x, 若 \(\lg x=y\), 则其位数为 \(\lfloor y+1 \rfloor\)
然后对于对数, 我们有 \(\lg \prod_{i=1}^x i= \sum_{i=1}^x \lg i\)
预处理前缀和之后在线 \(\Theta(1)\) 回答询问即可
- #include"cstdio"
- #include"cstring"
- #include"iostream"
- #include"algorithm"
- #include"cmath"
- using namespace std;
- const int MAXN=1e7+5;
- const double eps=1e-8;
- double lg[MAXN];
- int tp[MAXN];
- int T;
- int main()
- {
- for(int i=1;i<=1e7;++i) lg[i]=lg[i-1]+log10(i);
- for(int i=1;i<=1e7;++i) tp[i]=lg[i]+1;
- scanf("%d",&T);
- while(T--){
- int x;scanf("%d",&x);
- printf("%d\n",tp[x]);
- }return 0;
- }
来源: http://www.bubuko.com/infodetail-2869712.html