HDU 1525 Euclid's Game

题意:

给定两个数a和b,A和B轮流操作,每次可以用大的那个减去小的那个的若干倍数,要求减完非负。谁赢?

知识点:

博弈论

解法:

首先一个性质:设a>b,假如b<a<2b,接下来的操作肯定是唯一的,也就是胜败已定。

那么对于当前先手的人,如果a是b的倍数,那么他赢,假如a>2b,他也赢(因为他可以控制这一把到底变成b,a%b还是b,a%b+b,因为他可以预先推算变成上述性质的那个地方到底是N还是P,然后他会让对手变成P)。

否则继续暴力模拟下去。

原文地址:https://www.cnblogs.com/Ronald-MOK1426/p/12767199.html