백준 1850 : 1로만 된 최대공약수

(문제 원래 이름은 그냥 최대공약수인데 다른 최대공약수 문제를 풀었어서 헷갈릴까봐 다르게 표기함)

★★★☆☆
직접 최대공약수를 구하려고하니까 overflow가 발생해서,
일정 수준 이상으로는 정답이 안나왔다...알고보니 규칙을 잘못 파악했던 문제

<나의 풀이>

간단하게 두 숫자의 최대공약수를 구하고, 그 숫자만큼 1을 출력하면 된다.
원리를 이해하려고 증명식을 보았으나 이해하지 못했다.....
등비수열의 합 공식을 사용해서 증명한 글을 보았다.

최대공약수를 long long 타입 숫자에 담아 출력하려고 했는데,
숫자가 기하급수적으로 커지는지 오답이 나왔다.
그냥 바로바로 1을 출력하도록 하는게 훨씬 효율적이다.

#include <iostream>
using namespace std;

long long gcd(long long x, long long y) {
	long long r=0;
	while (y != 0) {
		r = x % y;
		x = y;
		y = r;
	}
	return x;
}

int main() {
	long long a, b;
	
	cin >> a;
	cin >> b;

	//cout << gcd(a, b) << "\n";
	long long ret = gcd(a, b);
	for (int i = 0; i < ret; i++) {
		cout << 1;
	}
	cout << "\n";
	return 0;
}

(고민한 시간에 비해 간단한 코드..)

<참고>

https://sexycoder.tistory.com/94
(증명글)