베주의 항등식 - 최대공약수로 만들 수 있는 정수

1. 문제 25333번: 개구리 (acmicpc.net) 25333번: 개구리 Albert는 개구리 장난감을 이용한 놀이를 즐겨한다. 이 장난감은 우측으로 $A$cm 혹은 좌측으로 $B$cm 점프할 수 있다. 예를 들어 현재 개구리 장난감의 위치가 $0$이고 $A = 4$, $B = 2$ 라 하자. 아래 그 www.acmicpc.net 2. 풀이 예제를 보면 A,B의 최대공약수의 배수의 개수가 정답일 것 같은데 조금 수학적으로 생각해보면 A,B로 만들 수 있는 자연수가 X 이내에 몇개나 있느냐?라는 문제와 같은데 오른쪽으로 x번 A만큼 점프하면 Ax가 되고 왼쪽으로 y번 B만큼 점프하면 By가 되니까, 만들 수 있는 정수는 Ax+By형태와 같다. 이는 베주의 항등식 형태와 같으며, "정수 x,y에 대하여..

• format_list_bulleted 정수론
• · 2023. 5. 27.
• textsms

확장된 유클리드 알고리즘(extended euclidean algorithm) 구현해보면서 익히기

1. 베주 항등식(Bézout's Identity) 적어도 하나가 0이 아닌 두 정수 a,b에 대하여 $$ax+by = gcd(a,b)$$ 를 만족하는 정수해 x,y가 반드시 존재한다. 여기서 정수해 x,y는 유일하지 않다. 왜냐하면, 양변에 ab를 더하고 빼보면 $$ax+ab + by-ab = gcd(a,b)$$ 이므로, $$a(x+b) + b(y-a) = gcd(a,b)$$ 이므로, (x,y)가 정수해라면, (x+b,y-a)도 정수해가 된다. 2. 유클리드 알고리즘(Euclidean algorithm) 최대공약수를 빠르게 구하는 알고리즘 - 유클리드 호제법 (tistory.com) 최대공약수를 빠르게 구하는 알고리즘 - 유클리드 호제법 1. 최대공약수 두 자연수 a,b가 공통으로 가지는 약수중에서 가장 큰..

• format_list_bulleted 정수론
• · 2022. 12. 16.
• textsms