두 셀로 S 만들기

시간 제한2초메모리 제한128 MB

요약

두 셀의 시작값이 a와 b일 때 한 셀의 값을 다른 셀에 반복해서 더해 S를 만들 수 있는지 판단합니다.

난이도: 보통10점 중 7점
유형: 정수론, 수학, 재귀
정답자: 아직 제출이 없습니다

문제

메모리 셀이 두 개인 컴퓨터가 있다. 두 셀의 이름은 a와 b이고, 셀에는 정수를 저장한다. 이 컴퓨터가 실행할 수 있는 명령은 a+=b와 b+=a 두 가지다. a+=b는 a에 저장된 값을 b의 값만큼 늘리고, b+=a는 b에 저장된 값을 a의 값만큼 늘린다.

프로그램은 이 두 명령을 늘어놓은 것이고, 명령은 적힌 순서대로 실행된다. 명령이 하나도 없는 빈 프로그램도 프로그램으로 친다.

a와 b의 처음 값, 그리고 목표 값 S가 주어진다. 실행이 끝났을 때 두 셀 중 하나에 S가 남는 프로그램을 만들 수 있는지 판정하는 프로그램을 작성하시오.

입력

첫째 줄에 a, b, S가 공백을 사이에 두고 주어진다. ( $0 \le a, b, S \le 10^{18}$ )

출력

두 셀 중 하나에 S가 남는 프로그램을 만들 수 있으면 YES를, 만들 수 없으면 NO를 출력한다.

예제3

예제 1
입력
```
1 2 3
```
예상 출력
```
YES
```
예제 2
입력
```
3 4 5
```
예상 출력
```
NO
```
예제 3
입력
```
3 4 17
```
예상 출력
```
YES
```