[BOJ] 14490 : 백대열 - travelbeeee

문제 : https://www.acmicpc.net/problem/14490

---

[알고리즘풀이]

1. 문자열로 입력받아, ':' 를 기준으로 숫자 2개(a, b)를 따로 저장한다.

2. 숫자 a, b는 최대 input이 100,000,000 이므로 최대 50,000,000을 공약수로 가질 수 있다.

따라서, 2부터 50,000,000가지 순회하며 공약수면 a, b를 계속 나눠준다.

#include<iostream>
#include<cmath>
#include<vector>
#include<string>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	string I, temp = {};
	cin >> I;
	int a,b, i = 0;
	while (I[i] != ':') {
		temp += I[i];
		i++;
	}
	a = stoi(temp);
	
	i++;
	string temp2 = {};
	while (i < I.size()) {
		temp2 += I[i];
		i++;
	}
	b = stoi(temp2);

	for (int i = 2; i < 50000001; i++) {
		if (a % i == 0 && b % i == 0) {
			while ((a % i == 0) && (b % i == 0)) {
				a /= i;
				b /= i;
			}
		}
	}
	cout << a << ':' << b;
}

---