每天一个TopCoder算法题（16.08.05）

这个题目来自TopCoder SRM 535 Div1 250分的题目 FoxAndGCDLCM。

原题

FoxAndGCDLCM

题意

有两个数，已知他们的最大公约数与最小公倍数，求这满足条件的两个数的和最小。不满足输出-1。数据范围是10^12次方。

思考

我们可以暴力地枚举这两个数，然后再分别求gcd与lcm，很明显，这种n*n的算法满足在数据超过10^6次方就难以忍受。
我们可以立马判断出一种非法的情况，就是lcm必须是gcd的倍数。
通常，最小公倍数我们可以分解质因数。我们发现，如果把这些数分成随机分成两部分，假设这两个数为x, y，那么lcm必定是这两个数的公倍数（不一定最小）。怎么变成是最小公倍数呢，x, y不能有相同的因子！
那我们又怎么满足gcd的条件呢？ 很简单，我们可以用lcm / gcd 的结果进行分解，最后得到的x, y再去乘以gcd， 就是我们想要的结果。
好了，问题分析到这里，我们已经有了下面思路:

• 素数筛选，我们需要筛选出10^{6以内的素数。(sqrt(10}12))
• 因式分解。
• 深度优先搜索，枚举因子分配。为什么可以深搜？因为10^12次方最多就只有十几个不同的因子。（2 x 3 x 7 x 11.。。。）

关键代码(JAVA)

素数筛选

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