[백준 1850] 최대공약수 (C++)

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

문제

---

모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.

예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다.

 

입력

---

첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 263보다 작은 자연수이다.

 

출력

---

첫째 줄에 A와 B의 최대공약수를 출력한다. 정답은 천만 자리를 넘지 않는다.

 

문제 풀이

---

유클리드 호제법을 이용한 문제.

 

입력은 1의 개수로 주어지지만 A와 B 모두 1로만 이루어져 있기 때문에, 입력한 수들의 최대공약수를 구해주면 된다. 예를 들어 1111과 111111은 111111과 1111이 모두 11로 나누어 떨어지기 때문에 답은 11이다. 각각 1이 4개, 1이 6개 존재하므로 1이 2개 존재하는 11이 최대공약수가 되는 것이다. 입력이 1의 개수로 주어지고 이 수들의 최대 공약수를 구하는 것이기 때문에, 이 최대 공약수는 정답에 존재하는 1의 개수가 된다. 빈 문자열에 1을 최대공약수의 개수만큼 붙여 답을 출력해주면 정답이다.

 

아래는 코드.

#include <iostream>
using namespace std;

long long getGCD(long long x, long long y)
{
	if (y == 0)
	{
		return x;
	}
	else
	{
		return getGCD(y, x % y);
	}
}

int main()
{
	long long x, y;
	cin >> x >> y;
	long long gcd = getGCD(x, y);
	string answer = "";
	answer.append(gcd, '1');
	cout << answer << "\n";
	return 0;
}