這個題目來自TopCoder SRM 535 Div1 250分的題目 FoxAndGCDLCM。

原題

FoxAndGCDLCM

題意

有兩個數(shù)，已知他們的最大公約數(shù)與最小公倍數(shù)，求這滿足條件的兩個數(shù)的和最小。不滿足輸出-1。數(shù)據(jù)范圍是10^12次方。

思考

我們可以暴力地枚舉這兩個數(shù)，然后再分別求gcd與lcm，很明顯，這種n*n的算法滿足在數(shù)據(jù)超過10^6次方就難以忍受。
我們可以立馬判斷出一種非法的情況，就是lcm必須是gcd的倍數(shù)。
通常，最小公倍數(shù)我們可以分解質(zhì)因數(shù)。我們發(fā)現(xiàn)，如果把這些數(shù)分成隨機(jī)分成兩部分，假設(shè)這兩個數(shù)為x, y，那么lcm必定是這兩個數(shù)的公倍數(shù)（不一定最?。?。怎么變成是最小公倍數(shù)呢，x, y不能有相同的因子！
那我們又怎么滿足gcd的條件呢？ 很簡單，我們可以用lcm / gcd 的結(jié)果進(jìn)行分解，最后得到的x, y再去乘以gcd， 就是我們想要的結(jié)果。
好了，問題分析到這里，我們已經(jīng)有了下面思路:

• 素?cái)?shù)篩選，我們需要篩選出10^{6以內(nèi)的素?cái)?shù)。(sqrt(10}12))
• 因式分解。
• 深度優(yōu)先搜索，枚舉因子分配。為什么可以深搜？因?yàn)?0^12次方最多就只有十幾個不同的因子。（2 x 3 x 7 x 11.。。。）

關(guān)鍵代碼(JAVA)

素?cái)?shù)篩選

    boolean number[] = new boolean[maxFactor];
    for (int i = 2; i < maxFactor; ++i){
        if (!number[i]){
            primes.add(i);
            for (int j = i + i; j < maxFactor; j += i){
                number[j] = true;
            }
        }
    }

因式分解

    private void doFactor(long num){
        for (long each : primes){
            while (num > 1 && num % each == 0){
                if (factors.containsKey(each)){
                    factors.put(each, factors.get(each) + 1);
                }else{
                    factors.put(each, 1);
                }
                num /= each;
            }
        }
        if (num > 1){
            factors.put(num, 1);
        }
    }

深搜枚舉

    private void find(long x, long y, int dep, List<Long> mulList){
        if (dep == mulList.size()){
            ret = x + y < ret ? x + y : ret;
            return;
        }
        find(x * mulList.get(dep), y, dep + 1, mulList);
        find(x, y * mulList.get(dep), dep + 1, mulList);
    }