1045 - Digits of Factorial
| Time Limit: 2 second(s) | Memory Limit: 32 MB |
Factorial of an integer isdefined by the following function
f(0)= 1
f(n) = f(n - 1) * n, if(n> 0)
So, factorial of 5 is 120. But in different bases, thefactorial may be different. For example, factorial of 5 in base 8 is 170.
In this problem, you have to find the number of digit(s) ofthe factorial of an integer in a certain base.
Input
Input starts with an integer T (≤ 50000),denoting the number of test cases.
Each case begins with two integers n (0 ≤ n ≤106) andbase (2 ≤ base ≤ 1000). Both ofthese integers will be given in decimal.
Output
For each case of input you have to print the case number andthe digit(s) of factorial n in the given base.
Sample Input |
Output for Sample Input |
|
5 5 10 8 10 22 3 1000000 2 0 100 |
Case 1: 3 Case 2: 5 Case 3: 45 Case 4: 18488885 Case 5: 1 |
题意：f[n]=n!，求f[n]在k进制下的位数。
思路：f[n]在k进制下的位数，即logk(f[n])=log10(f[n])/log10[k],打个1e6的表，表示10进制下f[n]的位数，即log10(f[n])，然后结果向上取整就行了，当n=0的时候加个特判。。。
ac代码：
#include<stdio.h>#include<math.h>
#include<string.h>
#include<stack>
#include<set>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#define MAXN 1010100
#define LL long long
#define ll __int64
#define INF 0x7fffffff
#define mem(x) memset(x,0,sizeof(x))
#define PI acos(-1)
#define eps 1e-10
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
//head
double a[MAXN];
void debug()
{
for(int i=1;i<=10;i++)
printf("%lf\n",a[i]);
}
void db()
{
a[0]=log10(1);
for(int i=1;i<=1000000;i++)
a[i]=a[i-1]+log10(i);
//debug();
}
int main()
{
db();
int t,i,j;
int n,k;
int cas=0;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
printf("Case %d: ",++cas);
if(n==0)
{
printf("1\n");
continue;
}
double ans;
ans=ceil(a[n]/log10(k*1.0));
printf("%d\n",(int)ans);
}
return 0;
}