#include <iostream>
using namespace std;
int div_N(int N1, int N2, int divN, int &count)
{
if ((N1 % divN == 0) || (N2 % divN == 0)) { count++; return div_N(N1 % divN, N2 % divN, divN, count); }
else { return count; }
}
int GCD(int a, int b)
{
if (b == 0) { return a; }
else return GCD(b, a % b);
}
int main()
{
int A, B, N;cin >> N;
for (int i = 0; i < N; i++)
{
cin >> A >> B;
int count = 0;
int gcd = GCD(A, B);
cout << gcd * (A / gcd) * (B / gcd) << endl;
}
return 0;
}
#include <iostream>
using namespace std;
//유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다.
//호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.
//2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
int div_N(int N1, int N2, int divN, int &count)
{
if ((N1 % divN == 0) || (N2 % divN == 0)) { count++; return div_N(N1 % divN, N2 % divN, divN, count); }
else { return count; }
}
int GCD(int a, int b)
{
if (b == 0) { return a; }
else return GCD(b, a % b);
}
int main()
{
int A, B; cin >> A >> B;
int count = 0;
int gcd = GCD(A, B);
cout <<gcd<< endl;
cout << gcd *( A / gcd ) * ( B / gcd ) << endl;
return 0;
}
'백준 > C++' 카테고리의 다른 글
[백준/C++] 1120번 문자열 (0) | 2020.11.23 |
---|---|
[백준/C++] 1439번 뒤집기 (0) | 2020.11.21 |
[백준/C++] 7568번 덩치 (0) | 2020.11.21 |
[백준/C++] 1010번 다리놓기 (0) | 2020.11.21 |
[백준/C++] 2755번 부녀회장이 될테야 (0) | 2020.11.14 |
댓글