bzoj 3000 Big Number 估算n!在k进制下的位数 斯特林公式

题目大意

求n!在k进制下的位数
2≤N≤2^31， 2≤K≤200

分析

作为数学没学好的傻嗨，我们先回顾一下log函数
(log_a(b)=frac 1 {log_b(a)})
(log_a (x^k)=k*log_a x)
(log_a(bc)=log_a(b)+log_a(c))
嗯嗯，呵呵

我们要求的是(log_k(n!))
n大处理不了
用斯特林公式
(n! approx sqrt{2pi n} * (frac n e)^n)
(log_k(n!)=frac 1 2log_k(2pi n)+n*log_k(frac n e))

注意

n小的时候暴力求
读入写了longlong
输出不longlong我是不是傻

solution

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef double db;
const db pi=acos(-1.0);
const db e=exp(1.0);

LL n,K;

db logk(db x){
	return log(x)/log(K);
}

int main(){
	int i;
	while(~scanf("%lld%lld",&n,&K)){
		if(n<=10000){
			db ans=0;
			for(i=1;i<=n;i++) ans+=logk(i);
			printf("%lld
",(LL)(1+ans));
		}
		else printf("%lld
",1+(LL)(logk(2*pi*n)*0.5+logk(n/e)*n) );
	}
	return 0;
}