CF1285C 题解
无敌的神
·
·
题解
思路
这道题本身就是一个大模拟水题。
先看题意是给定 X 求 \min(\max(a,b)) 其中 \operatorname{lcm}(a,b)=X。
其中 1\le X\le 10^{12}。
那么我们可以二重循环爆模拟，其中第一重枚举 a 第二重枚举 b。
又由题意知 b=\frac{X}{a},又结合辗转相除法时间复杂度可得此思路总时间复杂度为：
## AC 代码
```c
#include<bits/stdc++.h>
using namespace std;
long long x,a[10001],b[10001],k;
long long MIN=0xf7ffffff;
int lcm(int a,int b) {return a*b/__gcd(a,b);}
int main()
{
scanf("%lld",&x);
for(int i=1;i<=x;i++) {
for(int j=1;j<=x/i;j++) {
if(lcm(i,j)==x){
a[++k]=i;
b[k]=j;
}
}
}
for(int i=1;i<=k;i++) MIN=min(max(a[i],b[i]),MIN);
if(MIN/x>MIN) printf("%lld %lld",MIN,x/MIN);
else printf("%lld %lld",x/MIN,MIN);
}
```