3421-X-factor Chains

問題（外部リンク）

3421 -- X-factor Chains

実装の概要

例えばX=100であれば条件を満たす数列は
1,2,4,20,100
1,5,25,50,100
など計6パターンが有りえますが、ポイントとなるのはXを素因数分解した結果です。であることを考えると2つの2と2つの5をどの順番で掛けるかによってパターンが決まります（掛けてさえいれば必ず前の数で次の数を割り切れるような数列になります）。
問題では最長にすることが目標になっているので、そのためには合成数は使わずに素数のみを掛け続ければ求められます。
そのため、「Xは何回素数で割れるか」と「それぞれの素数で何回割ったか」を記録しておけばあとは順列の問題と同様に階乗を求めることで計算できます。
なお、素数テーブルは特に準備しなくても大丈夫です。

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while(true){
			String input = br.readLine();

			if(input == null){
				break;
			}

			solve(Integer.parseInt(input));
		}
	}

	static void solve(int n){

		int divisor = 2;

		//どの素数で何回割ったかを記録する
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

		int totalNum = 0;
		while(n > 1){
			//divisorで割り切れた場合
			if(n%divisor == 0){
				n /= divisor;
				totalNum++;

				if(map.containsKey(divisor)){
					map.put(divisor, map.get(divisor) + 1);
				}
				else {
					map.put(divisor, 1);
				}

				continue;
			}

			//割り切れなかったならdivisor更新
			divisor++;
		}

		Set<Integer> set = map.keySet();
		Iterator<Integer> it = set.iterator();

		long patterns = fact(totalNum);
		//それぞれの素数の個数の階乗で割る
		while(it.hasNext()){
			int tmp = it.next();

			patterns /= fact(map.get(tmp));
		}

		System.out.println(totalNum+" "+patterns);
	}

	//階乗を求める
	static long fact(int n){
		long result = 1;

		for(int i = n; i >= 1 ; i--){
			result *= i;
		}

		return result;
	}

}