本文主要是介绍zoj 4745 Factorial Problem in Base K，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
题目的意思就是：给一个k进制的数s，求s！在10 进制下的末尾0个数。
思路：
先把s转化为10进制下的数。
把n！分解质因数。
把k分解质因数。
求所有的k的质因数中，除以n！的相同质因数中最小的。就是answer。
例如：
看这组数据：10 10.
s本来就是10进制下的。所以不用转化。
10！=2^8*3^4*5^2*7
10=2*5;
看10 的质因数2为1个，对应的10！的的质因数2的个数为8. 8/1=8;
再看质因数5为1个，对应的 的质因数5的个数为2. 2/1=2;
所以answer=2；
描述不好。
代码：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define LL long long
const int N=105;
map<int,int> M;LL f(char *s,int k){LL len=strlen(s),n=0,mid=1;for(int i=len-1;i>=0;i--){n+=(mid*M[s[i]]);mid=mid*k;}return n;
}LL f1(LL x,int k){if(x<k) return 0;return x/k+f1(x/k,k);
}int Prime[20];
int top;
bool Judge(int x){int i;for(i=2;i<=(int)sqrt(x)&&x%i!=0;i++);if(i>(int)sqrt(x)) return true;return false;
}void Init(){top=0;for(int i=2;i<=62;i++)if(Judge(i)) Prime[top++]=i;top=top-1;
}int main(){Init();//A B C D E F G H I J K L M N O P Q R S T U V W X Y ZM['0']=0;M['1']=1;M['2']=2;M['3']=3;M['4']=4;M['5']=5;M['6']=6;M['7']=7;M['8']=8;M['9']=9;M['A']=10;M['B']=11;M['C']=12;M['D']=13;M['E']=14;M['F']=15;M['G']=16;M['H']=17;M['I']=18;M['J']=19;M['K']=20;M['L']=21;M['M']=22;M['N']=23;M['O']=24;M['P']=25;M['Q']=26;M['R']=27;M['S']=28;M['T']=29;M['U']=30;M['V']=31;M['W']=32;M['X']=33;M['Y']=34;M['Z']=35;M['a']=36;M['b']=37;M['c']=38;M['d']=39;M['e']=40;M['f']=41;M['g']=42;M['h']=43;M['i']=44;M['j']=45;M['k']=46;M['l']=47;M['m']=48;M['n']=49;M['o']=50;M['p']=51;M['q']=52;M['r']=53;M['s']=54;M['t']=55;M['u']=56;M['v']=57;M['w']=58;M['x']=59;M['y']=60;M['z']=61;char str[N];int k;while(~scanf("%s%d",str,&k)){LL n=f(str,k);//先把k进制的数转化成10进制的.LL num1[top+1],num2[top+1];memset(num1,0,sizeof(num1));memset(num2,0,sizeof(num2));for(int i=0;i<=top;i++){//将n分解质因数.num1[i]=f1(n,Prime[i]);}for(int i=0;i<=top;i++){//将k分解质因数.while(k%Prime[i]==0) {num2[i]++;k/=Prime[i];}}LL ans=-1;for(LL i=0;i<=top;i++){if(num1[i]&&num2[i]){if(ans==-1) {ans=num1[i]/num2[i];continue;}ans=min(ans,num1[i]/num2[i]);}}if(ans==-1) printf("0\n");else printf("%lld\n",ans);}return 0;
}
这篇关于zoj 4745 Factorial Problem in Base K的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
