洛谷P2252 取石子游戲(威佐夫博弈)

題目背景

無

題目描述

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

輸入輸出格式

輸入格式：

輸入共一行。

第一行共兩個數a, b，表示石子的初始情況。

輸出格式：

輸出共一行。

第一行為一個數字1、0或-1，如果最後你是勝利者則為1；若失敗則為0；若結果無法確定則為-1。

輸入輸出樣例

8 4

1

說明

[數據範圍]

50%的數據，a, b <= 1000

100%的數據，a, b <= 1 000 000 000

威佐夫博弈的裸題

不過不是那麼好AC，數據太刁鑽了

威佐夫博弈的必敗條件

$abs(a,b)*(1+\sqrt{5})/2 = min(a,b)$

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#define int long long 
using namespace std;
const int MAXN=1e6+10,INF=1e9+10;
main()
{
    int a,b;
    scanf("%lld%lld",&a,&b);
    if(a>b) swap(a,b);
    int temp=abs(a-b);
    int ans=temp*(1.0+sqrt(5.0))/2.0;
    if(ans==a) printf("0");
    else        printf("1");
    return 0;
}