#1261. 石子游戏

石子游戏

题目描述

Simon和Antisimon在玩石子游戏。

共有n颗石子,Simon先拿。

Simon能拿当前n和a的最大公约数,Antisimon能拿当前n和b的最大公约数。

当有一个人不能拿时(n=0)那个人就输了。

求谁赢了。

输入输出格式

输入格式

一行,a,b,n(1<=a,b,n<=100)

输出格式

一行,如果Simon赢了,输出0;Antisimon赢了,输出1.

样例 #1

样例输入 #1

3 5 9

样例输出 #1

0

样例 #2

样例输入 #2

1 1 100

样例输出 #2

1

说明

gcd(0,x)=gcd(x,0)=x;

对于样例1:

Simon拿gcd(3,9)=3颗

Antisimon拿gcd(5,6)=1颗

Simon拿gcd(3,5)=1颗

Antisimon拿gcd(5,4)=1颗

Simon拿gcd(3,3)=3颗

Antisimon输了

感谢@引领天下 提供的翻译