More actions
({CREATE}) |
No edit summary |
||
| Line 11: | Line 11: | ||
== 박인서 == | == 박인서 == | ||
#include <iostream> | |||
int gcd(int a, int b) { | |||
while (a%b != 0) { | |||
int t = a%b; | |||
a = b; | |||
b = t; | |||
} | |||
return b; | |||
} | |||
int main() { | |||
int a, b; | |||
std::cin >> a >> b; | |||
int c = b / a, r = 1; | |||
for (int i = 1; i*i <= c; i++) | |||
if (i*(c / i) == c && gcd(i,c/i)==1) r = i; | |||
std::cout << a*r << ' ' << a*c / r; | |||
return 0; | |||
} | |||
== 곽정흠 == | == 곽정흠 == | ||
| Line 18: | Line 40: | ||
== 박인서 == | == 박인서 == | ||
* 최대공약수를 a, 최소공배수를 b라 하면 b=a*x*y가 되도록 하면 두 수 a*x와 a*y가 원래의 두 수가 된다. | |||
* 이때 x와 y는 자연수여야 되고, 서로소여야한다. | |||
* 위의 아이디어를 이용하여 문제를 풀었다. | |||
== 곽정흠 == | == 곽정흠 == | ||
Revision as of 17:09, 19 September 2016
오늘의 문제
- [1]
- 추석이니 쉬운 문제로..
참가자
- 미시행
코드
15이원준
박인서
#include <iostream>
int gcd(int a, int b) {
while (a%b != 0) {
int t = a%b;
a = b;
b = t;
}
return b;
}
int main() {
int a, b;
std::cin >> a >> b;
int c = b / a, r = 1;
for (int i = 1; i*i <= c; i++)
if (i*(c / i) == c && gcd(i,c/i)==1) r = i;
std::cout << a*r << ' ' << a*c / r;
return 0;
}
곽정흠
아이디어
15이원준
박인서
- 최대공약수를 a, 최소공배수를 b라 하면 b=a*x*y가 되도록 하면 두 수 a*x와 a*y가 원래의 두 수가 된다.
- 이때 x와 y는 자연수여야 되고, 서로소여야한다.
- 위의 아이디어를 이용하여 문제를 풀었다.