A. Баатарлаг тоглоом

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Саймон Анти-саймонтой дараах тоглоомоор тоглож байлаа. Саймонд $a$ тоо Анти-саймонд $b$ тоо байгаа ба энэ тоо нь тоглоомын турш өөрчлөгдөхгүй.

Тэдэнд бас $n$ чулуутай хайрцаг өгөгджээ. Саймонгоос эхлэн тоглогчид ээлжиндээ тоглогч хайрцагнаас өөрийнх нь тогтмол ба хайрцганд байгаа чулууны тоо хоёрын хамгийн их ерөнхий хуваагчтай тэнцүү тоог авна. Ийнхүү ээлжилж тоглосоор үйлдлээ хийж чадахгүй болсон тоглогч хожигдоно. (Өөрөөр хэлбэл үйлдэл хийх үед нь хайрцганд чулуу байхгүй байвал).

Энэ тоглоомонд хэн нь хожихыг тодорхойл.

Оролт

Зайгаар тусгаарлагдсан $a$, $b$, $n$ ($1 ≤ a, b, n ≤ 100$) тоонууд өгөгдөнө.

Гаралт

Саймон хожвол "0", үгүй бол "1" гэж хэвлэнэ.

Орчуулсан: gmunkhbaatarmn

Жишээ тэстүүд

Оролт
3 5 9
Гаралт
0
Оролт
1 1 100
Гаралт
1

Тэмдэглэл

The greatest common divisor of two non-negative integers $a$ and $b$ is such maximum positive integer $k$, that $a$ is divisible by $k$ without remainder and similarly, $b$ is divisible by $k$ without remainder. Let $gcd(a, b)$ represent the operation of calculating the greatest common divisor of numbers $a$ and $b$. Specifically, $gcd(x, 0) = gcd(0, x) = x$.

In the first sample the game will go like that:

  • Simon should take $gcd(3, 9) = 3$ stones from the heap. After his move the heap has $6$ stones left.
  • Antisimon should take $gcd(5, 6) = 1$ stone from the heap. After his move the heap has $5$ stones left.
  • Simon should take $gcd(3, 5) = 1$ stone from the heap. After his move the heap has $4$ stones left.
  • Antisimon should take $gcd(5, 4) = 1$ stone from the heap. After his move the heap has $3$ stones left.
  • Simon should take $gcd(3, 3) = 3$ stones from the heap. After his move the heap has $0$ stones left.
  • Antisimon should take $gcd(5, 0) = 5$ stones from the heap. As $0 < 5$, it is impossible and Antisimon loses.

In the second sample each player during each move takes one stone from the heap. As $n$ is even, Antisimon takes the last stone and Simon can't make a move after that.

Сэтгэгдлүүдийг ачааллаж байна...