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



Sample input:
10 500
16 A
0 0


Sample output:
124
2

Submission status: Wrong Answer

Solution code:
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)):
        k=1
        p=prime[i]
        if pc[i]!=0:
            tmp=0
            while(p**k<L):
                e=L/p**k
                tmp+= e
                k+=1
            tmp/=pc[i]
        ans=min(ans,tmp)
    print ans

Submission status: Wrong Answer

Solution code:
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

Submission status: Wrong Answer

Solution code:
import string

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 / 2 + 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 = 1 << 30
    for f,n in fact:
        ff = f
        cnt = 0
        while ff <= num:
            cnt += num / ff
            ff *= f
        ans = min(ans, cnt / n)
    print ans

Submission status: Wrong Answer

Solution code:
import string

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 = 1 << 30
    for f,n in fact:
        ff = f
        cnt = 0
        while ff <= num:
            cnt += num / ff
            ff *= f
        ans = min(ans, cnt / n)
    print ans

Submission status: Wrong Answer

Solution code:
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 = INF
    for f,n in fact:
        ff = f
        cnt = 0
        while ff <= num:
            cnt += num / ff
            ff *= f
        ans = min(ans, cnt / n)
    print ans if ans != INF else 0

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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 = [] #tmp
    for f,n in fact:
        ff = f
        cnt = 0
        while ff <= num:
            cnt += num / ff
            ff *= f
        ans.append(cnt / n)
    print min(ans)