http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3621
Factorial Problem in Base K
Time Limit: 2 Seconds Memory Limit: 65536 KB
How many zeros are there in the end of s! if both s and s! are written in base k which is not necessarily to be 10? For general base, the digit order is 0-9,A-Z,a-z(increasingly), for example F4 in base 46 is actually 694 in base 10,and f4 in base 46 is 1890 in base 10.
Input
There are multiple cases(less than 10000). Each case is a line containing two integers s and k(0 ≤ s < 2^63, 2 ≤ k ≤ 62).
Output
For each case, output a single line containing exactly one integer in base 10 indicating the number of zeros in the end of s!.
Sample Input
101 2 12 7
Sample Output
3 1
Author:
ZHANG, DebingContest:
ZOJ Monthly, June 2012 zoj月賽題目，數據超強
那個求一個數n的階乘的因式分解中k的個數的寫的要精彩，才不會wa
code
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include<stdio.h>
#include <cassert>
#include <iostream>
#include <sstream>
#include <fstream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#include <iomanip>
#define maxn 205
using namespace std;
int hash[300];
char str[maxn*10];
long long k;
int fen[105];
int num[105],num1;
long long sum[105];
long long tmp;
#define pp printf("here\n")
long long change(char str[])
{
int i,len;
long long res;
len=strlen(str);
res=0;
for( i=0; i<len; i++)
{
res=res*k+hash[str[i]];
}
return res;
}
void fenjie()
{
int i;
long long tmpx=k;
memset(fen,0,sizeof(fen));
memset(num,0,sizeof(num));
num1=0;
for(i=2; i<=k; i++)
{
if(tmpx%i==0)
{
num1++;
fen[num1]=i;
while(tmpx%i==0) //這個地方，一定注意啊
{
num[num1]++;
tmpx=tmpx/i;
}
}
if(tmpx==1) break;
}
}
long long min(long long a,long long b)
{
return a<b?a:b;
}
long long chuli()
{
int i;
long long tmp1;
long long sumn;
long long xx;
memset(sum,0,sizeof(sum));
for( i=1; i<=num1; i++)
if(num[i]!=0&&fen[i]!=0)
{
// printf("%d %d\n",fen[i],num[i]);
xx=fen[i];
sumn=0;
tmp1=tmp;
while(xx<=tmp1)
{
sumn=sumn+tmp1/xx;
tmp1=tmp1/xx;
}
sum[i]=sumn;
}
long long res=sum[1]/num[1];
for( i=2; i<=num1; i++)
// if(num[i]!=0&&fen[i]!=0)
res=min(res,sum[i]/num[i]);
return res;
}
int main()
{
int i;
for( i=0; i<=9; i++)
{
hash[i+'0']=i;
//printf("%c,%d\n",i+'0',i);
}
for( i=0; i<26; i++)
{
hash[i+'A']=i+10;
// printf("%c,%d\n",i+'A',i+10);
}
for(i=0; i<26; i++)
{
hash[i+'a']=i+36;
// printf("%c,%d\n",i+'a',i+36);
}
while(scanf("%s%d",str,&k)!=EOF)
{
tmp=change(str);
// pp;
// printf("%I64u\n",tmp);
if(tmp!=0)
{
fenjie();
// pp;
// for(i=1;i<=num1;i++)
//printf("%d %d\n",fen[i],num[i]);
long long ans=chuli();
printf("%lld\n",ans);
}
else
{
printf("0\n");
}
}
return 0;
}