欧几里得游戏

53 阅读 0 评论 35 点赞

我是靠谱客的博主搞怪大米，最近开发中收集的这篇文章主要介绍欧几里得游戏，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：

一开始，板上写有两个不相等的正整数，两个玩家交替写数字，每一次，当前玩家都必须在板上写出任意两个板上数字的差，而且这两个数字必须是新的，也就是说，不能与板上任何一个已有的数字相同。当玩家再也写不出新数字时，他就输了。请问，你是选择先行动还是后行动呢？

分析：

其实这道题和欧几里得算法的减法版本有点像，只是有点拓展，无论他们怎么相减，最后肯定会得到最大公约数，假设最大公约数为m，那么两个正整数就是a = im， b = jm，既然得到了m，为了得到不同的数字，他们只能把所有m的倍数都写出来（有了一倍的情况，即m，肯定能得到其它倍数的情况km），最后他们得到的数字个数一定是：max(i, j)(包括最开始的2个数在内)。

因此，要判断先手还是后手，就取决于max(i, j) - 2的结果是奇数或偶数，奇数就先手，偶数就后手。

答案：

求得max(a, b) / gcd(a, b) - 2的结果，结果为奇数，先手；结果为偶数，就后手。