Codeforces Round #655 (Div. 2) B

文章目录[x]
  1. 1:题目链接
  2. 2:题面
  3. 3:题意
  4. 4:思路
  5. 5:参考代码




B

题目链接

https://codeforces.com/contest/1372/problem/B

题面

在这里插入图片描述

题意

对于给定的正整数,找两个数满足

思路

枚举的所有因子那么取最小即可。

参考代码

#include <algorithm>
#include <iostream>
#include <vector>
typedef long long LL;
using namespace std;
LL lcm(LL u, LL v) {
  LL h = __gcd(u, v);
  return (u * v / h);
}
int main() {
  LL t, n;
  cin >> t;
  while (t--) {
    cin >> n;
    vector<LL> ans;
    for (int i = 1; i * i <= n; i++) {
      if (n % i == 0) {
        ans.push_back(i);
        ans.push_back(n / i);
      }
    }
    LL minn = 1e18, min_ans = -1;
    for (LL i : ans) {
      if (i == n) {
        continue;
      }
      LL lc = lcm(i, n - i);
      if (lc < minn) {
        minn = lc;
        min_ans = i;
      }
    }
    cout << min_ans << " " << n - min_ans << endl;
  }
  return 0;
}


点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像