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; } }