题目链接:https://codeforces.com/contest/1372/problem/B
题意
给出一个正整数 $n$,找到两个正整数 $a,b$ 满足 $a+b = n$ 且 $LCM(a,b)$ 最小。
题解
$a$ 或 $b$ 中一定有 $n$ 的因子,枚举即可。
证明
若 $a,b$ 都不是 $n$ 的因子,则 $a,b,n$ 两两互素,$LCM(a,b) = a imes b$,当 $a = 1, b = n - 1$ 时,$LMC(a,b) = n - 1 < n$,除此外,$LCM(a,b) > n$ 。
若 $a,b$ 中有 $n$ 的因子,易得 $LCM(a,b) le n$,所以枚举因子即可。
代码
#include <bits/stdc++.h> using ll = long long; using namespace std; ll LCM(ll a, ll b) { return a * b / __gcd(a, b); } void solve() { int n; cin >> n; vector<int> div; for (int i = 1; i * i <= n; i++) { if (n % i == 0) { div.push_back(i); div.push_back(n / i); } } int ans_a = 1, ans_b = n - 1; for (int i : div) { if (i > 0 and n - i > 0 and LCM(i, n - i) < LCM(ans_a, ans_b)) ans_a = i, ans_b = n - i; } cout << ans_a << ' ' << ans_b << " "; } int main() { int t; cin >> t; while (t--) solve(); }