유클리드 호제법

문제설명

문제

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

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

입력

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

출력

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

접근

보통의 최대공약수는 유클리디안 알고리즘으로 구하면 되지만, 이 문제는 약간의 이해가 우선된다.

입력값은 모든 자리가 1로만 이루어져있는 자연수이고 자릿수가 주어진다. 입력값이 3과 4이면 111과 1111의 최대공약수를 구하는 것과 같다. 하지만 자릿수가 2⁶³보다 작은 자연수가 주어지기 때문에 기존의 유클리디안 알고리즘을 통해서는 구할 수 없다.

예제를 살펴보면 다음과 같은 특징을 발견할 수 있다. 자릿수를 통해 GCD를 구한 값이 출력 값의 자릿수임을 알 수 있다. 따라서 자릿수의 GCD를 구한 뒤 자릿수만큼 1을 출력하면 된다.

코드

#include <iostream>
using namespace std;

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

int main(){
	long long a, b, i;
	cin>>a>>b;
	for(i=0; i<gcd(a,b); i++)
		printf("1");
}

참고

BOJ #1850

이 글이 도움이 되셨다면 추천 클릭을 부탁드립니다 :)