题目链接: Fadi and LCM
大致题意
给定一个整数x, 要求你找到两个整数a和b, 满足 lcm(a, b) == x 并且 max(a, b) 尽可能小.
解题思路
通过题意, 我们不难想到, a和b两个数字应该是互质的两个数. 则 a和b 的所有质因子 应该和x的质因子相同.
然后我们光速开始写质因数分解, 现在问题就来了, 你怎么去分配这些质因子, 使得a和b尽可能接近呢?
到这里, 我们应该发现我们的思路就不太对了.
本题的正确思考角度是, 我们枚举x的所有约数对, 然后判断每个约数对的两个数是否互质即可.
最后输出最接近的互质约数对即可.
AC代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
int main()
{
ll x; cin >> x;
for (int i = sqrt(x); i >= 1; --i) {
if (x % i == 0 and gcd(i, x / i) == 1) {
cout << i << ' ' << x / i << endl;
break;
}
}
return 0;
}