1527 取石子游戏.cpp

ACM 威士忌部分答案

/*
先找规律，算几个很小的必败状态
1，2
3，5
4，7
6，10
8，13
...
发现所有的数恰在序列中出现一次
而且差为1，2，3，4，5，...
所以这两个序列构成正整数集的一个分划，猜想可以由betty定理生成（仅仅是猜想，不需要
太多的理由^_^）
其实，这两个序列恰好对应betty定理中alpha=(1+sqrt(5))/2,beta=(3+sqrt(5))/2的情况，
所以问题解决。

这题不算出公式的话是没法做的，因为规模太大，必败状态太多，没有任何的办法


betty定理是说，如果无理数alpha和beta满足
1.alpha,beta>0
2.1/alpha+1/beta=1
那么，序列{[alpha*n]}和{[beta*n]}构成自然数集的一个分划，其中[]是取整函数

这道题对应的alpha和beta分别是(1+sqrt(5))/2,(3+sqrt(5))/2
所以alpha=1/黄金分割
beta/alpha=黄金分割
可以说跟黄金分割有关，但也只是一种巧合吧，黄金分割还是经常出现的
*/

#include <cstdio>
#include <cmath>
using namespace std;

double a = (1.0 + sqrt(5.0)) / 2.0;
double b  = (3.0 + sqrt(5.0)) / 2.0;
	
int main()
{
	int big, small, n, t1, t2,t;
	while(scanf("%d %d",&big,&small)==2)
	{
		if(big < small)
		{
			t=big;
			big=small;
			small=t;
		}
		n = ceil(big / b);
		t1 = a * n;
		t2 = b * n;
		if(small == t1 && big == t2)
			printf("0\n");
		else printf("1\n");
	}
	return 0;
}