[알고리즘] 백준 1850번: 최대공약수 (C++)

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

1850번: 최대공약수

이번 문제는 TC를 통해 규칙을 파악했다.

TC #1
3 4
TC #2
3 6
TC #3
500000000000000000 500000000000000002

분명 주어진 입력값만큼 1의 개수라는 말인데 어째서인지 입력값끼리의 최대공약수도 똑같다는 것을 발견했다.

TC #2를 보면 3 6으로 111과 111111의 최대공약수를 구하는 것이다.

물론 111*1001 = 111111으로 최대공약수가 111이 될 수 있지만 정확한 이유는 파악하지 못했다.

여하튼 이번 문제는 입력값끼리의 최대공약수를 구하고, 최대공약수만큼 1을 출력하면 된다.

---

1) 유클리드 호제법으로 최대공약수 구하기

2) 자료형의 크기 (unsigned int -> long long)

 

1)

이제 최대공약수는 유클리드 호제법으로 구할 줄 알아야 한다.

다른 방법으로 구했다가는 시간 초과가 날 것이다.

 

2)

문제의 범위에서 2^63보다 작다는 것을 보고, unsigned int로 잡아두고 문제를 풀었지만 값을 넘어섰던 건지 이상한 값이 나왔었다.

하지만, 찾아보니

2^63 = 4,611,686,018,427,387,904

unsigned int의 범위 = 4,294,967,295

까지인 것을 보고 앞에 4만 보고 착각했구나 했다.

long long의 범위는 -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807까지이기 때문에 long long으로 풀 수 있었다.

---

[AC 코드]

#include <iostream>
using namespace std;
#define ui long long
#define MOD 10000000;

ui gcd(ui a, ui b) {
	if (a % b == 0) {
		return b;
	}
	return gcd(b, a % b);
}

int main() {
	ui a, b;
	cin >> a >> b;
	ui cnt = gcd(a, b) % MOD;

	while (cnt > 0) {
		cout << 1;
		cnt--;
	}
	return 0;
}