题目：
给出两个数，A，B轮流操作。每次操作可以将大的数减去小的数的整数倍，若操作后出现0，执行这次操作的人胜。
思路：
根据样例(25, 7)的提示，其实是非常容易想到的。从(25, 7)可以到达(11, 7)或者(4, 7)。易证这两个状态之间必定有一个会胜利，这时执行者就掌握了主动权。所以对于(a, b)，存在(max(a, b) \ge 2 * min(a, b))时必胜。还有当大的数是小的数的倍数的时候，也可以直接获胜。通过上面两个结论，就可以完成程序了。
实现：
经典POJ毒瘤，连数据范围都不给。要开(ll)
bool dfs(ll a, ll b)
{
if(a < b) swap(a, b);
if(a % b == 0) return true;
if(a >= 2ll * b) return true;
return !dfs(b, a - b);
}
Original: https://www.cnblogs.com/DM11/p/16749965.html
Author: DM11
Title: POJ 2348 Euclid’s Game（博弈论 辗转相减）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604625/
转载文章受原作者版权保护。转载请注明原作者出处！