HDU-1525 Euclid's Game

Euclid's Game

两个人进行博弈，轮流操作，给出两个数 \(a\) 和 \(b\) ，假设 \(b \ge a\)，则每次操作可以使得 \(b-ka\)，k为任意整数，并且必须保证操作后的 \(b\) 必须为正整数，先使得最小的数为 \(0\) 的获胜

博弈论分析

由于给出的 \(a\) 和 \(b\) 非常大，所以不能使用sg函数来分析，只能通过暴力或者博弈图分析

我们首先可以通过打表来判断一些初始状态：

• \((a, 0)\) 为必输态

• \((a, a)\) 为必胜态

接着分析，一些情况

• \((a, ka + r)\) 的时候（显然有约束 \(r < a\)， \(k\) 为整数）：

如果 \(k > 1\) 时，显然先手可以有操作使得，让自己转移到 \((a, r)\) 或者是让对方转移到 \((a, r)\) ，因为 \((a, r)\) 的必胜态、必输态是确定的，因此先手可以根据此来确定结局，所以此时 先手必胜

如果 \(k = 1\) 时，显然此时的先手没有任何选择，只能让状态转移到 \((a, r)\) ，然后记着上述的判断，直到0的出现

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include