很多人吐槽中国的企业喜欢看学历跟成绩，其实外国的企业也是这样！谷歌即便是社招也要你提供大学的成绩单，大企业往往比较关心你的数学水平，像这种数论题目也是经常出现的！
大家有什么意见建议请多多评论，有什么疑惑也说一说，小编会为大家解答！
原题
题意
有两个数，已知他们的最大公约数与最小公倍数，求这满足条件的两个数的和最小。不满足输出-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);
}
