首页 > 代码库 > UVA 10368 - Euclid's Game(数论+博弈)
UVA 10368 - Euclid's Game(数论+博弈)
10368 - Euclid‘s Game
题目链接
题意:Stan和Ollie玩游戏,有两个数字a,b,每次可以选择较小数字的倍数,把另一个数字-去这个数,要保证>= 0,最后谁那步能得出0谁就赢了,问谁会赢。
思路:其实这个相减的过程就是一个辗转相除的过程,考虑每一次辗转相除,如果只有1倍的数可以减,那么必须到下一步,如果有多步,先手的就有机会选择是自己到下一步或者让对方到下一步,这样先手的就必胜了,于是利用辗转相除,求出谁能先掌控局面,就是谁赢了。
代码:
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int n, m; void solve(int a, int b, int who) { if (!b || a / b > 1 || a == b) { printf("%s wins\n", who == 0? "Stan" : "Ollie"); return; } solve(b, a % b, !who); } int main() { while (~scanf("%d%d", &n, &m) && n + m) { if (n < m) swap(n, m); solve(n, m, 0); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。