2018全国多校算法寒假练习赛(三) A




Link

https://www.nowcoder.net/acm/contest/75/A

Type: 数论-Stirling公式

题意

给你一个n,问你n!的八进制位数是多少.

数据范围

有t(1~1000000)组数据
每组数据大小为 0~1000000

题解

由以上数据范围我们知道不能乱搞(暴力或者打表都会爆)了.
这里提第一个点:

求数M的K进制位数,答案就是

logK(M)+1

第二点:

n! 近似公式 – Stirling公式

结合这两点不难得出下列公式:

log8(n!) = M
=log8(sqrt(2*pi*n))+log8((n/e)^n)
=log8(sqrt(2*pi*n))+log8((n/e)^n)
=log8(sqrt(2*pi*n))+n*log8(n/e)
=ln(sqrt(2*pi*n))/ln(8)+n*ln(n/e)/ln(8)

常数时间就可以求出来了.

Code

#include<bits/stdc++.h>
using namespace std;
//M_PI,M_E
int main(){
    int t,n;
    cin>>t;
    for(int i=0;i<t;++i){
        scanf("%d",&n);
        if(n==0){
            printf("1\n");
            continue;
        }
        double ans=log(sqrt(2*M_PI*n))/log(8)+n*log(n/M_E)/log(8);
        printf("%d\n",(int)ans+1);
    }
    return 0;
}