[5347번] LCM

문제 출처 :

https://www.acmicpc.net/problem/5347

알고리즘 분석 :

문제 해결에 필요한 사항

1. 유클리드 호제법

2. GCD / LCM 코딩 :: http://www.crocus.co.kr/573

3. GCD / LCM 한줄 코딩 :: http://www.crocus.co.kr/578

무조건 위의 두 링크를 보고, 공부하고, 이 문제를 풀자.

설명할 것이 없다.

여기서 long long을 쓰는 이유는 lcm에서 a*b 과정에서 int형 이상으로 오버플로우가 날 수 있기 때문이다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

#include<iostream> using namespace std;   typedef long long ll;   ll gcd(ll a, ll b) { return !b ? a : gcd(b, a%b); } ll lcm(ll a, ll b) { return a*b / gcd(a, b); } int main() {     int tc;     scanf("%d", &tc);       while(tc--)     {         ll a, b;         scanf("%lld %lld", &a, &b);         cout << lcm(a, b) << endl;     }     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus