베주의 항등식 - 최대공약수로 만들 수 있는 정수
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에 대하여..