题目描述:
思路:博弈,对于给定的一组数(a,b),a>b,如果a%b!=0,那么就不能在当前组中决出胜负,一定会是在之后的某组中出现,即(b,a%b)
再往后推,直到a%b==0,此时先手就能胜利,然后就返回之前的那组,进行判断。
就假如有一组数(a,b),下一组是(b,a%b)。
假如(b,a%b)这种情况是先手必输的,那么(a,b)就先手必胜,因为只需要一次操作就能取到(b,a%b)
这种组合,然后让另一个人选,而(b,a%b)先手必输,那他就赢了,所以这种情况下(a,b)先手必赢
假如(b,a%b)这种情况是先手必赢得,那么就看a/b是否是大于1的,如果大于1,那么就在a中取(a/b-1)个b
就能得到(a%b+b,b)这种组合,而a%b+b是大于b的,而且只是b的一倍多,所以下一个人必定只能在(a%b+b)中
取一个b,得到组合(b,a%b),而(b,a%b)先手是必赢的,所以(a,b)在这种情况下也是必赢的。
反之,其余情况就是(a,b)先手就必输。
AC代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 10000005; const int inf = 0x3f3f3f3f; int check(int a, int b) { if (a%b==0) {return 1;}//a%b=0说明可以一次取到0,即先手必胜 int f = a / b, q = check(b, a % b); if (f>1||!q)return 1; return 0; } int main() { int t; scanf("%d", &t); while (t--) { int a, b; scanf("%d%d", &a, &b); if (a < b)swap(a, b);//a取大的数 if (check(a, b)) puts("Stan wins"); else puts("Ollie wins"); } return 0; }