[백준] 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의 개수가 주어진다. 입력되는 수는 $2^{63}$보다 작은 자연수이다.

---

출력

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

---

내 풀이

최대공약수를 구하는 문제는 너무 유명하다.

유클리드 호제법을 사용하면 된다.

---

코드

#include<iostream>

long long A, B, N;

long long g(long long a, long long b) {
	long long c;

	while (b != 0) {
		c = a % b;
		a = b;
		b = c;
	}

	return a;
}

int main() {
	scanf("%lld %lld", &A, &B);

	N = g(A, B);

	for (long long t = 0; t < N; t++) {
		printf("1");
	}

	return 0;
}