【题目来源】 https://www.luogu.com.cn/problem/P2252 【题目描述】 有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法：一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。 【输入格式】 输入共一行。 第一行共两个数 a,b，表示石子的初始情况。 【输出格式】 输出共一行。 第一行为一个数字 1,0 或 −1，如果最后你是胜利者则为 1；若失败则为 0；若结果无法确定则为 −1。 【输入样例】 8 4 【输出样例】 1 【数据范围】 50% 的数据满足 a,b≤1000； 100% 的数据满足 a,b≤10^9。 【算法分析】 ● 威佐夫博弈是一种两堆石子的公平组合博弈，双方轮流操作，既可以从任意一堆取走至少一颗石子，也可以从两堆同时取走同等数量的石子，取走最后一颗石子者获胜。威佐夫博弈的先手必败态，也就是奇异局势，可以由黄金分割比 φ=(1+sqrt(5))/2 刻画。即对于局面 (a,b)，设 a≤b，两堆石子的差值为 k=b-a，若 ⌊k・φ⌋ 等于较小数 a，则该局面为先手必败态，否则先手必胜。 ● 黄金分割比 φ 是无理数，浮点数无法保存其精确值，只能保存近似值。当差值 k 很大时，乘法运算会把浮点数的微小固有误差放大。即 k・φ 的浮点计算结果会略低于数学上的真实整数。同时，C++ 强制类型转换（long long）对浮点数采取直接截断小数部分的规则，并不会四舍五入，此时就会得到比正确值小 1 的整数，造成答案错误（WA）。因此本题本题采用 long double 配合 sqrtl()，提升有效存储位数，将误差压缩到不会改变整数部分的范围，以此通过全部测试数据。 例如，k・φ 的数学真值为 100000000.00000000，受浮点近似误差影响，计算机计算得到 99999999.99999998。此外，C++ 的 (long long) 强制转换直接截断小数部分，于是 (long long)(99999999.99999998) 得到 99999999，最终算出的 ⌊k・φ⌋ 相比真实数学结果少 1，导致判题错误。 补充备注：该现象不是 double 一定会发生，是大数场景下有概率发生。long double 也不是绝对无误差，只是本题数据范围下误差不足以改变整数部分。 ● 比如，如下代码因未使用 long double，会导致有一个大数测试样例不通过。即输入“433494437 701408733”时，输出 0，而不是正确的 1。
#include <bits/stdc++.h>
using namespace std;
int main() {
int a,b;
cin>>a>>b;
if(a>b) swap(a,b);
double phi=(1+sqrt(5))/2;
int k=(int)((b-a)*phi);
if(k==a) cout<<"0\\n";
else cout<<"1\\n";
return 0;
}
【算法代码】
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
LL a,b;
cin>>a>>b;
if(a>b) swap(a,b);
long double phi=(1.0L+sqrtl(5.0L))/2.0L;
LL k=(LL)((b-a)*phi);
if(k==a) cout<<"0\\n";
else cout<<"1\\n";
return 0;
}
/*
in:433494437 701408733
out:1
*/
【参考文献】 https://www.luogu.com.cn/problem/solution/P2252
