6380: 取石子游戏

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:31 Solved:4

Description

Simon和Antisimon在玩石子游戏。
共有n颗石子,Simon先拿。
Simon能拿当前n和a的最大公约数,Antisimon能拿当前n和b的最大公约数。
当有一个人不能拿时(n=0)那个人就输了。
求谁赢了。

Input

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

Output

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

Sample Input Copy

3 5 9

Sample Output Copy

0

HINT

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输了