백준 1850 파이썬 최대 공약수를 유클리드 호제법

백준 1850 - 최대공약수

문제

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

1850번: 최대공약수

1850번

답안 코드 :

def gcd(a, b):

    if b == 0:

        return a

    else:

        return gcd(b, a % b)

a, b = map(int, input().split())

result = gcd(a, b)

while result > 0:

    print(1, end='')

    result -= 1

생각 :

# 문제 분석
# 예제 3번을 보면 단순한 방법으로 최대 공약수를 찾을 수 없다
# 규칙을 찾아보자면
# 수의 길이를 나타내는 두 수의 최대 공약수는 A와 B의 gcd 길이를 나타낸다.

# 문제 풀이
# A B 의 최대 공약수를 유클리드 호제법을 이용해서 구하기
# 공약수 길이만큼 1 반복출력

 

정수론 정리 글들

 

https://mkisos.tistory.com/entry/%EC%A0%95%EC%88%98%EB%A1%A0-%EC%86%8C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B1%84

정수론 : 소수 구하기 에라토스테네스의 채

 

https://mkisos.tistory.com/entry/%EC%A0%95%EC%88%98%EB%A1%A0-%EC%98%A4%EC%9D%BC%EB%9F%AC-%ED%94%BC

정수론 : 오일러 피

https://mkisos.tistory.com/entry/%EC%A0%95%EC%88%98%EB%A1%A0-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95

정수론 : 유클리드 호제법

https://mkisos.tistory.com/entry/%EC%A0%95%EC%88%98%EB%A1%A0-%ED%99%95%EC%9E%A5-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95

정수론 : 확장 유클리드 호제법