본문 바로가기
백준/C++

[백준/C++] 1934번 최소공배수, 2609번 최대공약수와 최소공배수

by 뷕뺙쀡 2020. 11. 21.
#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

댓글