Codeforces Beta Round 90 |
---|
Закончено |
Семен и Антисемен играют в игру. Изначально каждому игроку дано одно фиксированное целое положительное число, которое не меняется в процессе игры. Семену дано число a, Антисемену дано число b. Также у них есть кучка из n камней. Игроки ходят по очереди, первый ход делает Семен. На своем ходу игрок должен взять из кучки число камней, равное наибольшему общему делителю данного ему числа и количества оставшихся камней в кучке. Проигрывает тот, кто не сможет взять требуемое число камней (по причине того, что в кучке остается строго меньше камней, чем нужно взять).
Ваша задача — по заданным a, b и n определить, кто выиграет в этой игре.
В единственной строке через пробел записаны целые числа a, b и n (1 ≤ a, b, n ≤ 100) — числа, данные Семену и Антисемену соответственно, и исходное количество камней в кучке.
Если выиграет Семен, выведите «0» (без кавычек), иначе выведите «1» (без кавычек).
3 5 9
0
1 1 100
1
Наибольшим общим делителем двух неотрицательных целых чисел a и b называется такое наибольшее положительное целое число k, что a делится на k без остатка, и, аналогично, b делится на k без остатка. Обозначим через gcd(a, b) операцию вычисления наибольшего общего делителя чисел a и b. В частности, gcd(x, 0) = gcd(0, x) = x.
В первом примере игра будет идти следующим образом:
Во втором примере каждый игрок на каждом ходу берет из кучки по одному камню. Так как n четное, последний камень возьмет Антисемен, а Семен после этого не сможет сделать ход.
Название |
---|