题目地址
题目大意:
两个人st和ol博弈
有两个整数n,m
每次轮到一个人时候,需要选择用大的那个数减去小的那个数的倍数(不能减为负数)
最后得到0的为胜利者
思路:
(以下讨论均在n<m的条件下)
一.
首先考虑一种简单的情况m/n==1
那么每次轮到的人就只有一种选择m-n
然后还满足上述条件,则重复
二.
m/n>=2
假设m=kn+p
假设(n,p)是一个必胜点
当前状态为(n,m)
但是当前的操作者不想把这个必胜点留给对方
所以这个操作者选择转移到(n,m-(k-1)*n) –>(n,n+p)
因为p的范围是[0,n-1]
轮到第二个操作者的时候,他只能选择一种操作(即第一种情况)然后这个必胜点就又回到来一号操作者的手中
假设(n,p)是一个必败点
那么一号操作者可以由(n,m)直接转移到(n,z)把这个必败点留给对方
综上:
n/m>=2时,当前操作者必胜
具体操作:
就是第一种情况就是一直while循环过来循环过去就行, 遇到第二种情况就退出
复杂度不太会分析
这种方法的时间复杂度是多少呢?不难发现,当ii和jj为斐波那契数列的相邻两项时,所需次数最多。得出,复杂度上界略大于O(logn)O(logn)。肯定是不会炸的!
–来自洛谷一位大佬
Code:
n = read(), m = read();
if(n > m) swap(n, m);
if(m / n >= 2)
puts("Stan wins");
else
{
int flag = 1;
while(1)
{
if(n > m) swap(m, n);
if(m % n == 0||m/n>=2) break;
ll t = n;
m -= t;
n = n;
flag = 1 - flag;
}
if(flag)
puts("Stan wins");
else
puts("Ollie wins");
}