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月賽題目，數(shù)據(jù)超強(qiáng)
那個(gè)求一個(gè)數(shù)n的階乘的因式分解中k的個(gè)數(shù)的寫的要精彩，才不會(huì)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) //這個(gè)地方，一定注意啊
{
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;
}