SRM534-div1-2-EllysNumbers

zz: http://www.strongczq.com/2012/03/srm534-div1-2-ellysnumbers.html

題目原文：http://community.topcoder.com/stat?c=problem_statement&pm=11787&rd=14727

題目大意：      給定一個整數n（取值範圍[2,10^18]）,以及互不相等的正整數（取值範圍[1,10^9]）集合，集合大小取值範圍為[1,500]，問：有幾種方式可以将n表示成集合中幾個互質的正整數的乘積(可以是一個正整數)。

思路：      這道題題目相當的簡短，非常贊！      看完題目，我首先是挖掘了一下“将n表示成幾個互質的正整數的乘積”這個内容，其實包含了一個非常有意義的含義。比如n=x*y*z，如果将這幾個數都進行質因子分解，那麼我們可以發現x，y，z必然不會有公共的質因子，并且它們的質因子肯定屬于n的質因子，且對應的指數也必須是相同的。是以正整數集合中的值肯定是不能亂取。這個分析結果先放着。      再考慮一下解法，這一題比較明顯可以看出來應該使用DP了。用sp[]表示這個正整數集合。DP的狀态方程為f(pos,s)，表示隻考慮整數集合中pos之後的元素，有幾種方法可以将s表示成互質的正整數的成績。 題目的答案可以表示成f(0,n)。狀态轉移方程為:

• 如果sp[pos]與n/s互質：f(pos,s) = f(pos + 1,s) + f(pos + 1, s / sp[pos]) 
• 否則：f(pos,s) = f(pos + 1,s)

     狀态邊界是f(sp.length, 1)=1。      現在分析一下資料規模，pos的取值範圍可以是[0,500)，s的取值範圍...我擦...居然是[1,10^18]。這必須不靠譜的！别急，這個時候我們就需要用之前的分析結果。由于正整數集合中隻有滿足一定條件的元素才是有意義的，這個條件是：

• 必須能被n整除
• 所有的質因子的指數與n的質因子的指數相同。

     在dp之前，我們先把所有不符合以上條件的元素都幹掉。把s進行質因子分解，則所得到的質因子肯定是n的質因子，且指數部分必然相同。假設n的質因子個數為p，則s最多隻能取2^p個值。那麼p會有多大，考慮最小的那一批質數的乘積：      2*3*5*7*11*13*17*19*23*29*31*37*41*43*47=614,889,782,588,491,410      總共15個質數，是以p肯定不會大于15，那麼狀态總數最大可以接近500×2^15，考慮最終的傳回是long類型，是以f(pos,s)的取值也必須是long的，64MB記憶體必然超了。我一開始沒有分析好，覺得貌似ok就寫代碼了，而且還是用HashMap<Long, Long>來存中間狀态的遞歸DP實作，結果system test時輕松time out了。      是以這道題的難點又是如何用省記憶體并高效的方式來儲存中間狀态了。其實考慮到s的可能取值那麼少，完全可以想辦法避免将其值作為狀态儲存。可以想到的一種表示狀态的方法是，用二進制掩碼來表示s是否包含某一個質因子，這樣可以使用0到2^15來表示這些狀态。那麼可以使用long[500][2^15]來表示中間狀态，為了節省記憶體，我們可以進一步發現，由于每一步f(pos,s)最多依賴于pos+1時的狀态值，是以在疊代實作的DP算法中完全不需要記錄500個pos下的狀态，隻需要2個，互相交替使用。是以隻需要long[2][2^15]的記憶體消耗即可搞定。後來看官方題解發現，其實隻需要long[2^15]就足夠記錄狀态了，見代碼中的注釋。      前面其實還有一個難題忽視掉了，那就是怎麼對可以達到10^18的n進行質因子分解？本人所知道的比較土的方法隻能以O(sqrt(n))的複雜度進行質因子分解，是以直接分解n必然要冒着逾時的危險。是以這裡需要用到一個小技巧，那就是對整數集合中的每個整數（經過前面的條件帥選的）進行質因子分解，得到所有的質因子（包括指數的值），然後把這些因子全都乘起來，如果等于n，那麼就得到n的質因子分解結果了；如果不等于n那必須傳回0了。

Java代碼：

public class EllysNumbers {
    private long gcd(long a, long b) {
        return a == 0 ? b : gcd(b % a, a);
    }

    private boolean isOK(long n, int x) {
        if (n % x != 0) {
            return false;
        }
        n /= x;
        if (gcd(n, x) == 1) {
            return true;
        }
        return false;
    }

    private void findFactors(int x, Set<Integer> factorSet) {
        for (int i = 2; i * i <= x; ++i) {
            int f = 1;
            while (x % i == 0) {
                x /= i;
                f *= i;
            }
            if (f != 1) {
                factorSet.add(Integer.valueOf(f));
            }
        }
        if (x != 1) {
            factorSet.add(Integer.valueOf(x));
        }
    }

    public long getSubsets(long n, String[] special) {
        StringBuilder sb = new StringBuilder();
        Set<Integer> factorSet = new HashSet<Integer>();
        for (String s : special) {
            sb.append(s);
        }
        String[] strSps = sb.toString().split(" ");
        int cnt = 0;
        int[] sp = new int[500];
        for (String s : strSps) {
            int x = Integer.parseInt(s);
            if (isOK(n, x)) {
                sp[cnt++] = x;
                findFactors(x, factorSet);
            }
        }
        int[] factors = new int[factorSet.size()];
        long product = 1;
        int c = 0;
        for (Integer f : factorSet) {
            product *= f.intValue();
            factors[c++] = f.intValue();
        }
        if (product != n) {
            return 0;
        }
        int[] mask = new int[cnt];
        for (int i = 0; i < cnt; ++i) {
            for (int j = 0; j < factors.length; ++j) {
                if (sp[i] % factors[j] == 0) {
                    mask[i] |= (1 << j);
                }
            }
        }
        long[] mem = new long[1 << factors.length];
        mem[(1 << factors.length) - 1] = 1;
        for(int p = cnt - 1; p >=0 ; --p){
            for(int m = 0; m < (1 << factors.length); ++m){
                if((m & mask[p]) == 0){
                    //m狀态隻依賴于m | mask[p]，而m | mask[p]肯定大于m，
                    //是以mem[m | mask[p]]的值必然還是上一次疊代的結果，尚未被破壞
                    mem[m] += mem[m | mask[p]];
                }
            }
        }
        return mem[0];
    }
  }