[C++] 최대 공약수, 최소 공배수

1. 최대 공약수

int gcd(int a, int b)
{
	int n;

	while (b != 0) {
		n = a % b;
		a = b;
		b = n;
	}

	return a;
}

 

2. 최소 공배수

int lcm(int a, int b)
{
	return a * b / gcd(a, b);
}

 

ex)

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

1735번: 분수 합

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<stack>
#include<string>
#include<map>
using namespace std;

int gcd(int a, int b)
{
	int n;

	while (b != 0) {
		n = a % b;
		a = b;
		b = n;
	}

	return a;
}

int lcm(int a, int b)
{
	return a * b / gcd(a, b);
}

int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	int lc = lcm(b, d);
	int re = a * (lc / b) + c * (lc / d);

	int rlc = lc;
	int rre = re;
	//! 최대공약수로 약분
	rlc = lc/ gcd(re, lc);
	rre = re / gcd(re, lc);

	cout << rre << ' ' << rlc;
	
}