본문으로 바로가기

Codeforces Round #613 Div2. C - Fadi and LCM 1250Pts.

 

Problem - C - Codeforces

 

codeforces.com

Q. 임의의 X에 대해 LCM(a,b) = X를 만족하는 a,b중 max(a,b)를 최소로 하는 a,b 구하기


LCM(a,b) = a * b / GCD(a,b) 이므로

X가 정해진 이상 max(a,b)를 최소로 하기 위해선 a*b/GCD(a,b)를 최소로 해야 하며,

GCD(a,b)가 1일때 max(a,b)는 최소가 될 수 있다.

 

 

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
26
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline ll gcd(ll b, ll s) {
    return (s==0LL)?b:gcd(s, b%s);
}
int main() {
    ll mn=0x3f3f3f3f3f3f3f3fLL,a=0,b=0;
    ll n; scanf("%lld"&n);
    for(ll i=1; i*i<=n; i++) {
        if(n%i == 0) {
            ll j=n/i;
            if(gcd(i,j) == 1LL) {
                if(max(i,j) < mn) {
                    mn = max(i,j);
                    a=i; b=j;
                }
            }
        }
    }
    printf("%lld %lld\n", a,b);
    return 0;
}
 
cs