HDU 1525 Euclid's Game【博弈 PN找规律】

题目传送门：hdu1525 Euclid’s Game

题意： 两个数，两人轮流操作，大数可以减去小数的整数倍（不能为负），先到0者为赢。

---

对某个状态(a, b) a >= b 最简单的情况，如果a%b == 0, 则先手必赢。 a > 2*b时，也是先手必赢，因为(a%b+b, b)状态必定与(a%b, b)相反，(a, b)可以转移到其中的必败态。 a < 2*b时，只能转移到(a-b, b)，状态与其相反， 继续向下转移即可获知当前状态。

#include <cstdio> #include <algorithm> using namespace std; int main(int argc, char const *argv[]) { int a, b; while(scanf("%d%d", &a, &b), a&&b) { if(a < b) swap(a, b); bool win = true; while(1) { if(a % b == 0 || a >= b << 1) break; a -= b; swap(a, b); win = !win; } if(win) puts("Stan wins"); else puts("Ollie wins"); } return 0; }