目录

题目：

题目描述：

思路：

AC代码：

---

题目：

题目描述：

给你一个长整型 X 

①你需要找到一对 a 和 b ，使得 LCM（a，b） == X 

②你需要保证 max(a，b) 是所有符合①条件中最小的（若有多种情况输出其中一种即可）

思路：

首先，要满足①条件，我们可以发现

LCM（a，b） == a * b / GCD（a，b）

X == a * b / GCD（a，b）

然后，我们再去思考②，不妨设（a>=b）

在满足①下，若 GCD（a，b）> 1 ，让 a1 = a / GCD（a，b），同时自然有 GCD（a1，b） == 1

此时也能满足 LCM（a，b） == a1 * b / GCD（a1，b）

而，max（a1，b）必定小于 max（a，b）

所以只有在GCD（a，b）== 1 的时候才有可能找到一对合适的 ab 使得 max（a，b）最小

所以，整合一下两条结论

a * b == X 

GCD（a，b） == 1

思路有了，具体操作请看AC代码

AC代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e5 + 5;

ll gcd(ll a, ll b)
{
	return (b == 0 ? a : gcd(b, a % b));
}

void solve()
{
	ll x;
	cin >> x;
	ll a = 1, b = 1;

	for (ll i = (ll)sqrt(x + 1); i >= 1; i--)
	{
		if (x % i)
			continue;
		if (gcd(i, x / i) == 1)
		{
			a = max(i, x / i);
			b = min(i, x / i);
			break;//越接近X的平方根的，max（a，b）必定越小，所以可以提前跳出
		}
	}
	cout << a << " " << b << '\n';
}

int main()
{
	std::ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	while (t--)
		solve();
	return 0;
}