【POJ】1067.取石子游戏

题解

这道题让我对SG函数有了更深刻的理解，这是道打表找规律题
我们打出来SG函数似乎是
1 2必败
3 5必败
4 7必败
6 10必败
8 13必败
哇我找到规律了……
然而，我显然不会通项
后来百度题解这个东西是威佐夫博弈，前面东西的通项是
(lfloor frac{sqrt{5} + 1}{2} floor * (b - a))
orzzzz好吧

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
//#define ivorysi
#define MAXN 200005
#define eps 1e-8
using namespace std;
typedef long long int64;
typedef double db;
db u = (sqrt(5.0) + 1) / 2;
int a,b;
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    while(scanf("%d%d",&a,&b) != EOF) {
	if(a > b) swap(a,b);
	if(floor((b - a) * u) == a) puts("0");
	else puts("1");
    }
}