読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 534 Div1 Medium: EllysNumbers

解法

そもそも、specialの中の整数を互いに素になるように組み合わせてnが作れるのかチェックする。出来るのであればbitDPするだけ。

コード

import java.util.ArrayList;
import java.util.Map;
import java.util.TreeMap;

public class EllysNumbers {

	public long getSubsets(long n, String[] input) {
		// 入力を受け取る
		StringBuilder sb = new StringBuilder();
		for (String s : input) {
			sb.append(s);
		}
		String[] tmp = sb.toString().split(" ");
		ArrayList<Integer> special = new ArrayList<Integer>();
		int contains1 = 1;
		for (String x : tmp) {
			int t = Integer.parseInt(x);
			if (t == 1) {
				contains1 = 2;
			} else if (n % t == 0) {
				special.add(t);
			}
		}

		// specialの累乗でnが作れるかどうか調べる
		Map<Integer, Integer> primeFactor = new TreeMap<Integer, Integer>();
		ArrayList<Integer> usableSpecial = new ArrayList<Integer>();
		for (int x : special) {
			int curX = x;
			boolean isUable = true;
			for (int prime = 2; prime * prime <= x; prime++) {
				if (curX % prime == 0) {
					int zz = 1;// primeの累乗でxの約数である最大のもの
					while (curX % prime == 0) {
						curX /= prime;
						zz *= prime;
					}

					// nがzzよりも多くprimeで割れる場合、そもそもxは採用されない
					if ((n / zz) % prime == 0) {
						isUable = false;
						break;
					}
					primeFactor.put(prime, zz);
				}
			}

			if (isUable && curX != 1) {
				if ((n / curX) % curX == 0) {
					isUable = false;
				} else {
					primeFactor.put(curX, curX);
				}
			}
			if (isUable)
				usableSpecial.add(x);
		}

		// そもそもspecialだけでnが作れないならば終了
		for (Map.Entry<Integer, Integer> e : primeFactor.entrySet()) {
			n /= e.getValue();
		}
		if (n != 1) {
			return 0;
		}

		// bitDPに向けてprimeのリストを作る
		ArrayList<Integer> primes = new ArrayList<Integer>();
		for (Map.Entry<Integer, Integer> e : primeFactor.entrySet()) {
			primes.add(e.getKey());
		}

		// usableなspecialがどのprimeを含んでいるか
		int[] usableBitmask = new int[usableSpecial.size()];
		for (int i = 0; i < usableSpecial.size(); i++) {
			for (int j = 0; j < primes.size(); j++) {
				if (usableSpecial.get(i) % primes.get(j) == 0) {
					usableBitmask[i] |= 1 << j;
				}
			}
		}

		// bitDP
		long[] dp = new long[1 << primes.size()];
		dp[0] = 1;
		for (int bitmask : usableBitmask) {
			for (int i = 0; i < dp.length; i++) {
				if ((i | bitmask) == (i ^ bitmask)) {
					dp[i | bitmask] += dp[i];
				}
			}
		}

		return dp[dp.length - 1] * contains1;
	}

}