poj 1067-石取りゲーム（威佐夫のゲーム）

http://poj.org/problem?id=1067
砂利取りゲーム
Time Limit: 1000 MS
 
メモリLimit: 100000 K
Total Submissions: 36753
 
Acceepted: 12446
Description
二つの石があります。数量は自由で、違います。ゲームは二人で順番に石を取ります。ゲームの規定では、毎回2種類の取り方があります。一つは任意の山の中から任意の石を取ってもいいです。二つの山の中で同じ量の石を同時に取り出すことができます。最後に石を全部取った方が勝ちです。最初の2つの石の数を与えます。順番が来たら、両方とも最善の策を講じると仮定して、最後に勝者ですか？それとも敗者ですか？
Input
入力はいくつかの行を含み、いくつかの石の初期状況を表し、各行は負でない整数aとbを含み、2つの石の数を表し、aとbはいずれも1,000,000,000,000,000を超えない。
Output
出力の対応もいくつかの行があります。1行に1つの数字が含まれています。最後に勝者がいれば1、反対に0です。
Sample Input

2 1

8 4

4 7

Sample Output

0

1

0

 
 
これはウェイゾフのゲームです。ウィゾフゲームとはACMの問題でよく見られる組み合わせゲームの一つです。大体このようなものです。二つの石があります。まず一つの山に10があると考えてもいいです。もう一つの山には15があります。互いに順番にいくつかの石を取ります。合法的な取り方は次の二つがあります。2、二つの石の中から同じぐらいのどれかを取ってください。最後の石を取ると約束した人は勝者となり、必勝の策略を求める。
二つの石の位置は同じです。残りの石の数（a、b）で状態を表します。状態は必敗状態、必勝状態、可能勝利状態があります。例えば：（0、0）は必ず負けます。（0，k），（k，0），（k，k）シリーズのノードは必勝状態に違いない。分析してみると、必败态は（0、0）、（1、2）、（3、5）、（4、7）、（6、10）、（8、13）、（9、15）、（11、18）、（12、20）などがあります。必敗状態（ak，bk）については、ak=[k*(1+√5)/2]、bk=ak+k(k=0,1,2,・・n)があります。中には、括弧は整理関数を表します。必敗の状態に対して、先に手を取る者は負ける。非必敗状態に対しては先取者が勝つ。数学の証明については、ブロ友の文章を参考にしましょう。
コード:

 1 #include <fstream>

 2 #include <iostream>

 3 #include <cstdio>

 4 #include <cmath>

 5 

 6 using namespace std;

 7 

 8 int main()

 9 {

10     //freopen("D:\\input.in","r",stdin);

11     //freopen("D:\\output.out","w",stdout);

12     int a,b;

13     double m=(sqrt(5.0)+1)/2;

14     while(~scanf("%d%d",&a,&b)){

15         if(a<b){

16             a^=b;

17             b^=a;

18             a^=b;

19         }

20         int k=a-b;

21         if(b==(int)(k*m))

22             puts("0");

23         else

24             puts("1");

25     }

26     return 0;

27 }