CodeForces 1372B Omkar and Last Class of Math(思维，数学，好题)

101 阅读 0 评论 67 点赞

我是靠谱客的博主整齐钢笔，这篇文章主要介绍CodeForces 1372B Omkar and Last Class of Math(思维，数学，好题)，现在分享给大家，希望可以做个参考。

题意：给出一个n，求满足a+b=n且lcm(a, b)最小的a和b。

题解：显然当a,b存在倍数关系的时候lcm是最小的，我们可以想想把n平均分成若干等份，然后a为其中一份，剩下的全部为b，这样a,b一定可以构成倍数关系，并且显然份数越少我们的lcm越小。即找到最小的n的因子x,输出n/x,n-n/x即可。

AC代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
const int maxn=1e6+5;
main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int flag=1;
for(int i=2;i<=n/i;i++){
if(n%i==0){
cout<<n/i<<" "<<n-n/i<<endl;
flag=0;
break;
}
}
if(flag)cout<<1<<" "<<n-1<<endl;
}
}