学步园

题目链接：点击打开链接

题目的意思就是：给一个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 Z
    M['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;
}