Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-19SRM370 (Practice)

SRM 370 NumberOfDivisors

|  SRM 370 NumberOfDivisors - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 370 NumberOfDivisors - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7863

  • 約数がちょうどk個の数の中で、最小のものを求める
    • p={2,3,5,7, ... } を素数の列とする。
    • A = p1^a1*p2^a2* ... * pn^an と素因数分解できるとき、約数の個数は (1+a1) * (1+a2) * ... * (1 + an)個
    • [掛け算の結果][素数をどこまで使ったか]の最小値でDPする
    • 素数は47まで考えれば十分 (2*3*5*...*53 > 10^18なので)
  • 練習ではオーバーフローしてWA
    • BigIntegerに書き換えたら通った。

import java.math.BigInteger;
import java.util.Arrays;

public class NumberOfDivisors {
	public long smallestNumber(int k) {
		if (k <= 2) {
			return k;
		}
		int[] p = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
		int pl = p.length;
		
		long limit = (long)Math.pow(10, 18);
		BigInteger blimit = BigInteger.valueOf(limit);
		long[][] dp = new long[50001][pl+2];
		for (int i = 0 ; i < 50001 ; i++) {
			Arrays.fill(dp[i], Long.MAX_VALUE);
		}
		dp[1][0] = 1;
		for (int a = 1 ; a < k ; a++) {
			for (int b = 0 ; b < pl ; b++) {
				if (dp[a][b] != Long.MAX_VALUE) {
					for (int c = 0 ; (c+1) * a <= k ; c++) {
						if (k % ((c+1) * a) == 0) {
							if (Math.pow(p[b], c) <= 0 || Math.pow(p[b], c) > limit) {
								break;
							}
							BigInteger from = BigInteger.valueOf(dp[a][b]);
							BigInteger mul = BigInteger.valueOf((long)Math.pow(p[b], c));
							if (from.multiply(mul).compareTo(blimit) > 0){
								break;
							}
							long willgo = dp[a][b] * (long)Math.pow(p[b], c);
							dp[(c+1)*a][b+1] = Math.min(dp[a][b] * (long)Math.pow(p[b], c), dp[(c+1)*a][b+1]);
						}
					}
				}
			}
		}
		long l = Long.MAX_VALUE;
		for (int i = 1 ; i <= pl ; i++) {
			if (dp[k][i] != Long.MAX_VALUE) {
				l = Math.min(l, dp[k][i]);
			}
		}
		
		if (l == Long.MAX_VALUE || l > limit) {
			return -1;
		}
		
		return l;
	}
}