AOJ2086 !

問題リンク !

• 概要

整数NとN進数で表現された文字列Mが与えられる。N進数でM!を計算したとき、末尾に続く0の数を10進数で出力せよ。なお、10を超える整数はA〜Zで表現されるものとする。
8 <= N <= 36

M

<= 12

• 解法

この問題の応用編になります。
まずNを素因数分解し、必要な素数と個数を調べます。そして、M!に含まれる素因数の個数を調べ、Nを作れる個数を数え答えとします。
M!に含まれる素因数を数えるために、上述した問題にある通り除算を繰り返す方法が使えます。Mの10進数最大は
36 ZZZZZZZZZZZZ
という場合ですが実はこれはsigned 64-bit型に収まります。よって除算の方法が使えます。

• ソース

import java.util.Scanner;

//!
public class AOJ2086 {

	void run(){
		Scanner sc = new Scanner(System.in);
		int[] p = {2,3,5,7,11,13,17,19,23,29,31};
		for(;;){
			int n = sc.nextInt();
			char[] s = sc.next().toCharArray();
			if(n==0)break;
			long X = 0;
			for(char c:s){
				long x = 'A'<=c?(c-'A'+10):(c-'0');
				X = X*n+x;
			}
			long[] need = new long[11];
			int N = n;
			for(int i=0;i<11;i++){
				if(N%p[i]==0){
					N/=p[i];
					need[i--]++;
				}
			}
			long[] num = new long[11];
			for(int i=0;i<11;i++){
				long x = X;
				while(x>1){
					num[i]+=x/p[i];
					x/=p[i];
				}
			}
			long res = Long.MAX_VALUE;
			for(int i=0;i<11;i++)if(0<need[i])res=Math.min(res, num[i]/need[i]);
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2086().run();
	}
}