Problem:
Problem C: ! You are one of ICPC participants and in charge of developing a library for multiprecision numbers
and radix conversion. You have just finished writing the code, so next you have to test if it
works correctly. You decided to write a simple, well-known factorial function for this purpose:   Your task is to write a program that shows the number of trailing zeros when you compute M !
in base N , given N and M . Input The input contains multiple data sets. Each data set is described by one line in the format
below:  N M  where N is a decimal number between 8 and 36 inclusive, and M is given in the string repre-
sentation in base N . Exactly one white space character appears between them. The string representation of M contains up to 12 characters in base N . In case N is greater
than 10, capital letters A, B, C, ... may appear in the string representation, and they represent
10, 11, 12, ..., respectively. The input is terminated by a line containing two zeros. You should not process this line. Output For each data set, output a line containing a decimal integer, which is equal to the number of
trailing zeros in the string representation of M ! in base N . Sample Input 10 500
16 A
0 0 Output for the Sample Input 124
2

Solution (Python):
import string

while(1):
    [N,M]=raw_input().split()
    N=int(N)
    if N==0: break
    S=string.digits+string.ascii_uppercase

    prime=[2,3,5,7,11,13,17,19,23,29,31]
    pc   =[0 for i in range(len(prime))]
    ans=999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
    for i in range(len(prime)):
        n=N
        while(1):
            if n%prime[i]==0:
                n/=prime[i]
                pc[i]+=1
            else:
                break
    L=0
    for i in range(1,len(M)+1):
        c=M[-i]
        L += S.index(c)*N**(i-1)
    
    for i in range(len(prime)):
        p=prime[i]
        if pc[i]!=0:
            k=1
            tmp=0
            while(p**k<=L):
                e=L/p**k
                tmp+= e
                k+=1
            tmp/=pc[i]
            ans=min(ans,tmp)
    print ans

Solution (Python):
import string
INF = 1 << 30

def conv(base, num):
    ret = 0
    for n in str(num):
        if n in string.ascii_letters:
            n = ord(n) - ord("A") + 10
        else:
            n = int(n)
        ret = ret * base + n
    return ret

def get_fact(n):
    ret = []
    for i in xrange(2, n + 1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n /= i
        if cnt != 0:
            ret.append((i, cnt))
    return ret

while True:
    base, num = raw_input().split()
    if (base, num) == ("0", "0"):
        break
    base = int(base)
    num = conv(base, num)
    fact = get_fact(base)
    ans = [] 
    for f,n in fact:
        ff = f
        cnt = 0
        while ff <= num:
            cnt += num / ff
            ff *= f
        ans.append(cnt / n)
    print min(ans)