백준 파이썬 1850번 - 최대공약수

1850번: 최대공약수

1로만 이루어져있는 수들을 차례로 소인수분해하거나, 최대공약수를 구하다보면 규칙성이 보이기 시작한다 

두 자연수 A와 B의 1의 개수가 a, b개라면 A,B의 최대공약수는 a,b의 최대공약수와 같다 

즉, gcd(A,B) = gcd(a,b)인 것이다

그러므로 gcd(a,b)=k라면 1이 k개로 구성된 수가 정답이 된다 

 

def gcd(a,b):
	if b == 0:
		return a 
	aa = a%b
	return gcd(b,aa)
a, b = map(int,input().split())
k = gcd(a,b) #정답은 k만큼의 1이 들어간 수가 되는 것 
print('1'*k)