[C++] 백준 1934: 최소공배수

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

1934번: 최소공배수

아이디어

A와 B의 인수를 모두 곱한다.

풀이

A의 인수를 map<int, int> 형식의 aliquots_A라는 변수에 담았다.  key에는 인수를 value에는 그 개수를 저장했다. B에서도 마찬가지로 같은 형식의 aliquots_B라는 변수에 같은 방식으로 저장했다. 2부터 시작하여 A(또는 B)가 1이 될 때까지 나눌 수 있으면 나누는 방식으로 인수를 구했다. 그리고 aliquots_A의 각 key를 순회하며 B에서 같은 key의 value와 비교하여 더 작으면 B의 value 값으로 대치한 뒤, B의 key를 지웠다. 이후 남은 key들을 각각 value만큼 곱해나가면 답이 나온다.

코드

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define EL "\n"

int main() {
#ifdef DEBUG
	//	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int T, A, B;
	cin >> T;
	while (T--) {
		cin >> A >> B;

		map<int, int> aliquots_A, aliquots_B;
		for (int i = 2; A > 1; i++) {
			while (A % i == 0) {
				A /= i;
				aliquots_A[i]++;
			}
		}

		for (int i = 2; B > 1; i++) {
			while (B % i == 0) {
				B /= i;
				aliquots_B[i]++;
			}
		}

		for (auto& aliquot_A : aliquots_A) {
			auto& [key, val] = aliquot_A;
			if (val < aliquots_B[key])
				val = aliquots_B[key];
			aliquots_B.erase(key);
		}

		int product = 1;
		for (auto& aliquot_A : aliquots_A)
			FOR(i, aliquot_A.second)
			product *= aliquot_A.first;
		for (auto& aliquot_B : aliquots_B)
			FOR(i, aliquot_B.second)
			product *= aliquot_B.first;
		cout << product << EL;
	}

	return 0;
}