题意：坑爹题意不明显。最后才理解是什么意思
给一个k进制的数和进制k，求这个数在十进制下的结果(这个结果在2^63范围内)的阶乘表示为k进制的话末尾有多少个0
比如说样例给的
101 2
表示101是二进制表示形式，把它表示为10进制是5，5!=5*4*3*2*1=120，它的二进制是：1111000，末尾有三个0，所以输出的是3
思路：
我们把这题的问题转换为：
假设s是阶乘的结果
求1~s中包含有多少个k
理由：这个很好想到的。我们可以逆向思考，假设xxx000，x表示未知的，我们可以清晰的看到，这个结果包含3个0，我们可以很容易想到，是有3个10相乘得到的结果。那么我想知道，到底是1?可以包含3个10呢？然后想一下。10是有2和5组成的对吧？那么我们就可以转换为。1?中一定要包含3个2,3个或以上的5。
现在我们再转换成正向思考，假设我知道了s，我想知道1~s中到底包含多少个2，多少个5，我取它们之间的最小值就是s!末尾的0的数目了。因为min(2的数目，5的数目)一定是10的个数。
我们总结一下：
我们想知道10进制下s!末尾是0的个数，我们就得知道1~s中包含了多少个10。
那么我们想知道k进制下s!末尾是0的个数，我们就得知道1s中包含了多少个k。
这样的话我们就需要对k进行质因数分解了。
另：如果我们知道s，怎么求1~s中包含2的个数？
要理解这句话的意思。假设s是6
1~6中包含多少个2？答案是4个
为什么？2(1) 4(2) 6(1) 不就是4个吗？要知道4是包含有两个2的。
那该怎么求1~s中包含2的个数。
我们另k=s/2，那么k一定是包含2个数，但是这k个数中，可能还有2的倍数，那么再k/2，直到k<2为止
那么我们就有了一个简易的代码：求1~s中包含k的个数
int ret=0;
while(s>=k){
ret+=s/k;
s/=k;
}
|
好了，详情看代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
char str[10000];
int k;
int getnum(char s){
if(s>='0'&&s<='9')return s-'0';
else if(s>='A'&&s<='Z')return 10+s-'A';
else return 10+26+s-'a';
}
int zyz[70][100]={0};
int zys[70][100]={0};
void dosome(int sum){
int &num=zyz[sum][0];
int tmp=sum;
num=0;
for(int i=2;i<=sum;i++){
if(tmp%i==0){
zyz[sum][++num]=i;
int cnt=0;
while(tmp%i==0){
++cnt;
tmp/=i;
}
zys[sum][i]=cnt;
}
}
return ;
}
int main()
{
for(int i=2;i<70;i++){
dosome(i);
}
while(~scanf("%s%d",str,&k)){
long long s=0;
long long tk=1;
for(int i=strlen(str)-1;i>=0;i--){
s+=tk*getnum(str[i]);
tk*=k;
}
long long n1=-1;
for(int i=1;i<=zyz[k][0];i++){
long long cnt=0;
long long tmp=s;
while(zyz[k][0]<=tmp){
cnt+=tmp/zyz[k][i];
tmp/=zyz[k][i];
}
cnt/=zys[k][zyz[k][i]];
if(n1==-1)n1=cnt;
else if(n1>cnt)n1=cnt;
}
printf("%lld\n",n1);
}
return 0;
}
|
