루미 알고리즘

#1658브론즈Compass Rotations

PO 2026 학교 예선코딩출제 Harry Zhang영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

You have a compass that can point in 360 different directions. Right now it points straight up, at the number 0.

Unfortunately, the compass is broken! The only way you can make it point in other directions is by lifting the whole compass and rotating it a number of degrees counterclockwise. To help you, you have two robot arms. Unfortunately, these are not perfect: the first robot arm can spin the compass exactly a degrees counterclockwise and the second robot arm can spin it b degrees counterclockwise. The robot arms can only rotate the compass exactly a and b degrees, respectively, each time they are used, no more and no less. Because of this, it may not be possible to make the compass point in all 360 directions.

This makes you wonder, how many unique directions can the compass point in? Write a program that figures this out given the numbers a and b. Note that since we rotate in a circle, a rotation of 10 degrees counterclockwise is the same as a rotation of 370 degrees counterclockwise; that is, 0 and 360 are the same number of degrees. More generally, we only care about the remainder of the number of degrees rotated divided by 360.

Input

The first line of input contains the integer a (1 ≤ a ≤ 360), the number of degrees the first robot arm spins the compass.

The second line contains the integer b (1 ≤ b ≤ 360), the number of degrees the second robot arm spins the compass.

Output

Print an integer: the number of unique directions the compass can be pointed in.

Scoring

Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.

GroupPointsConstraints
120a = 13
240a = b
340No additional constraints.

예제

예제 1

입력
50
180
출력
36

예제 2

입력
360
360
출력
1

출처 표기

출처: Programmeringsolympiaden 2026년 학교 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.