light oj 1045 Digits of Factorial (k进制数的位数)
题目链接 题意：求n！在k进制表示下有多少位。 思路：答案为[ log(1)+log(2)+…+log(N) ]+1 其中log的底数都是K
由于有多组数据，预处理一个log的前缀和。
代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :Tue 13 Sep 2016 05:13:15 PM CST 4File Name :code/loj/1045.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <set>-digits-of-factorial-k进制数的位 13#include <map> 14#include <string> 15#include <cmath> 16#include <cstdlib> 17#include <ctime> 18#define fst first 19#define sec second 20#define lson l,m,rt<<1 21#define rson m+1,r,rt<<1|1 22#define ms(a,x) memset(a,x,sizeof(a)) 23typedef long long LL; 24#define pi pair < int ,int > 25#define MP make_pair 26using namespace std; 27const double eps = 1E-8; 28const int dx4[4]={1,0,0,-1}; 29const int dy4[4]={0,-1,1,0}; 30const int inf = 0x3f3f3f3f; 31const int N=1E6+7; 32int n; 33int base; 34double sum[N]; 35int main() 36{ 37 #ifndef ONLINE_JUDGE 38 freopen("code/in.txt","r",stdin); 39 #endif 40 sum[0] = 0 ; 41 for ( int i = 1 ; i < N ; i++) sum[i] = sum[i-1] + log(i); 42 int T; 43 cin>>T; 44 int cas = 0 ; 45 while (T--) 46 { 47 scanf("%d%d",&n,&base); 48 double ans = sum[n]/log(base)+1; 49 printf("Case %d: %d\n",++cas,int(ans)); 50 } 51 #ifndef ONLINE_JUDGE 52 fclose(stdin); 53 #endif 54 return 0; 55}