동전 시스템

A, B, X가 주어질 때, 두 동전 X와 Y로 만들 수 있는 가격 집합이 A와 B로 만드는 집합과 정확히 같아지는 Y의 개수를 구하고, 무한히 많으면 -1을 출력한다.

보통7정수론수학그리디아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

영선이가 사는 나라에는 두 종류의 동전 A와 B가 있다. 이 나라의 모든 제품 가격은 A×p+B×qA \times p + B \times q (ppqq는 음이 아닌 정수) 꼴이므로 두 동전만 있으면 충분하다.

어느 날 영선이는 다른 동전 시스템으로도 이 나라의 모든 제품 가격을 만들 수 있는지 궁금해졌다.

A, B, X가 주어질 때 A×p+B×qA \times p + B \times q 꼴의 가격을 모두 만들 수 있는 두 동전의 가치를 구하는 프로그램을 작성하시오. 한 동전의 가치는 X이고 다른 동전의 가치는 Y(YXY \neq X)이다. X는 입력으로 주어지므로 Y를 구하는 것이 문제이다. 새 시스템에서도 각 동전은 음이 아닌 정수 개만큼 쓸 수 있고, Y는 양의 정수이다.

입력

첫째 줄에 A, B, X가 주어진다. (1A,B,X2001 \le A, B, X \le 200)

출력

첫째 줄에 가능한 Y의 개수를 출력한다. 가능한 Y가 무한히 많으면 -1을 출력한다.