杭電1527 取石子遊戲（威佐夫博弈模闆）

取石子遊戲

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 3760    Accepted Submission(s): 1892

Problem Description 有兩堆石子，數量任意，可以不同。遊戲開始由兩個人輪流取石子。遊戲規定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時取走相同數量的石子。最後把石子全部取完者為勝者。現在給出初始的兩堆石子的數目，如果輪到你先取，假設雙方都采取最好的政策，問最後你是勝者還是敗者。  

Input 輸入包含若幹行，表示若幹種石子的初始情況，其中每一行包含兩個非負整數a和b，表示兩堆石子的數目，a和b都不大于1,000,000,000。  

Output 輸出對應也有若幹行，每行包含一個數字1或0，如果最後你是勝者，則為1，反之，則為0。  

Sample Input

2 1
8 4
4 7
        

Sample Output

0
1
0
        

Source NOI  

/*
威佐夫公式m(k)=k*(1+√5)/2 
	n(k)=m(k)+k; 簡單變形一下m(k)=(n(k)-m(k))*(1+根号5)/2 
反正其實直接記得結論 加油！！！
Time:2014-10-19 12:33
*/ 
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int main(){
	int n,m,k;
	while(scanf("%d%d",&n,&m)!=EOF){
		if(m>n)swap(n,m);
		k=n-m;
		int temp=(int)(k*(1+sqrt(5.0))/2.0);
		if(temp==m)
			printf("0\n");
		else
			printf("1\n");
	}
return 0;
}