Codeforces Round #613 Div2. C - Fadi and LCM 1250Pts.
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 |
'PS - OJ > Codeforces' 카테고리의 다른 글
XOR 문제. bit단위로 max(a_i xor X)를 최소로 하는 값 구하기 (0) | 2020.01.12 |
---|---|
LIS(Longest Increasing Subsequence) 구하는데 정확히는 Subsequence가 모두 붙어있는 수열(Substring)을 구하는 경우. (0) | 2020.01.11 |
[Codeforces] Two Pointers Div2. C~D 난이도 (Update 19.12.29) (0) | 2019.12.27 |
Codeforces Round #443 (Div. 1) A. Short Program (0) | 2017.12.10 |
Codeforces Round #439 (Div. 2) E. The Untended Antiquity (0) | 2017.10.12 |