「BZOJ3000」Big Number

2014年8月12日3,8130

Description

给你两个整数N和K,要求你输出N!的K进制的位数。

Input

有多组输入数据,每组输入数据各一行,每行两个数——N,K

Output

每行一个数为输出结果

Sample Input

2 5
2 10
10 10
100 200

Sample Output

1
1
7
69
对于100%的数据,有2≤N≤2^31, 2≤K≤200,数据组数T≤200。

题解

用Stirling公式求近似值

位数=logk(n!)+1

≈ logk(sqrt(2πn)*(n/e)^n)+1

= logk( sqrt(2πn))+log[(n/e)^n]+1

=1/2*logk( 2πn)+nlog(n/e)+1

=0.5*logk ( 2πn)+nlog(n/e)+1

=0.5*logk ( 2πn)+nlog(n)-nlog(e)+1

PS:pi=acos(-1.0),e=exp(1)

PS2:eps的存在是为了防止n=2,k=2这样刚好的情况出现,这个时候向上取整要多取1位

 

avatar
  Subscribe  
提醒