取对数求阶乘位数——lightoj1045

/*
求 n! 在base进制下的位数 
取对数，用换底公式，预处理对数前缀和 
b^x = n!
x = log_b(n!) 
  = log_10(n!)/log_10(b)
对x向上取整即可 
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
double sum[maxn];
void init(){
    for(int i=1;i<maxn;i++)
        sum[i]=sum[i-1]+log(1.0*i);
}

int main(){
    init();
    int t;cin>>t;
    for(int i=1;i<=t;i++){
        long long n,b;
        cin>>n>>b;
        double ans=sum[n]/log(1.0*b);
        if(n==0)ans=0;
        printf("Case %d: %lld
",i,(long long)(ans)+1);
    }
}