날먹문제
솔직히 이게 왜 실4인지 잘 모르겠다.
5347번: LCM
첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다.
www.acmicpc.net
유클리드 호제법 씌운 GCD를 이용하면
빠르게 구할수 있다.
#include <stdio.h>
typedef long long int ll;
ll gcd(ll a, ll b){
while(b!=0){
ll r = a%b;
a = b;
b = r;
}
return a;
}
ll lcm(ll a, ll b){
return a*b/gcd(a,b);
}
int main(){
int n;
ll a, b;
scanf("%d", &n);
for(int i=0; i<n; i++){
scanf("%lld %lld", &a, &b);
printf("%lld\n", lcm(a,b));
}
return 0;
} 반응형