题目描述
给你两个整数N和K，要求你输出N！的K进制的位数。
输入
有多组输入数据，每组输入数据各一行，每行两个数——N，K
输出
每行一个数为输出结果。
样例输入
2 5
2 10
10 10
100 200
样例输出
1
1
7
69
题解
数论
题目转化一下变为求$lfloorlog_kn! floor+1$，使用换底公式，问题转化为求$log n$。
$n$有$2^31$之大，显然不能暴力去求。
这里需要用到Stirling公式：$n!approxsqrt{2pi n}(frac ne)^n$。这个公式在$n$较大时比较精确，因此可以直接套用；当$n$较小时精确度没有那么高，因此需要小范围暴力。
直接使用cmath中的函数对右半部分取对数即可（右半部分化简结果为$frac 12log 2pi n$+nlogfrac ne），再除以$log k$，下取整+1即为答案。
注意需要long long。
#include <cmath>
#include <cstdio>
const double pi = acos(-1) , e = exp(1);
int main()
{
int n , k , i;
while(~scanf("%d%d" , &n , &k))
{
if(n <= 100)
{
double ans = 0;
for(i = 1 ; i <= n ; i ++ ) ans += log(i);
printf("%d
" , (int)floor(ans / log(k)) + 1);
}
else printf("%lld
" , (long long)floor((log(2 * pi * n) / 2 + log(n / e) * n) / log(k)) + 1);
}
return 0;
}