【codechef】【May Challenge 2019 Division 2】【Matches】题解

[题目链接](https://www.codechef.com/MAY19B/problems/MATCHS) ### 题目描述 给定 $n,m$，两个人在玩游戏 每次每个人需要把较大的数字减去较小的数字的若干倍，不能减 $0$，以及不能减成负数 谁不能操作谁输 其中 $1 \le n,m \le 10^{18}$ ### 题解 实际上是求 $\gcd$ 的过程 也就是现在有 $\log(n)$ 个变量 $x_1 \sim x_{m}$，然后两个人依次操作这些变量，只有当前变量为 $0$ 时才能操作下一个变量 每次可以把当前变量变小，但不能不变，同时不能小于 $0$ 不妨求一遍 $SG$ 函数，发现实际上只需要把所有变量和 $2$ 取 $\min$ 即可