최대공약수

아래와 같이 두 정수 와 가 있다.

초기 상태의 , 에 대하여, 그 둘의 최대공약수를 라고 하자.

당신의 목표는, , 또는 , 인 상태를 만드는 것이다.

이를 위해 당신은 다음과 같은 여섯 종류의 작업을 최대 300번 실행할 수 있다.

• "A *= 2" : 의 값을 두 배로 만든다.
• "B *= 2" : 의 값을 두 배로 만든다.
• "A /= 2" : 가 짝수일 때, 의 값을 절반으로 만든다.
• "B /= 2" : 가 짝수일 때, 의 값을 절반으로 만든다.
• "A -= B" : 일 때, 에서 를 뺀다.
• "B -= A" : 일 때, 에서 를 뺀다.

"RESET" 버튼을 누르면 모든 작업을 취소하고 초기 상태로 돌아간다. "UNDO" 버튼을 누르면 가장 최근에 한 교환을 취소한다.

실행할 수 없는 작업인 경우, 버튼은 자동으로 비활성화된다.

문제를 해결하는 도중에 제출하면 현재까지 한 작업이 저장된다.

문제 형식

인터랙티브

출처

• KOI 2022 1차대회 고등부 1교시 17번
• KOI 2022 1차대회 중등부 1교시 19번