题意:2个人轮流对数进行操作, 每次都将大的那个数减去小的那个数的任意倍数但是不能变成负数, 现在谁能使得某一个数变成0, 谁就赢得了比赛。
题解:如果每次 a/b == 1 也就是说 a 只能减去一个 b的话, 那么这2个人就开始轮流的进行大数减小数, 如果这个cnt 是奇数 那么是先手赢 否则后手赢。
但是如果遇到a/b > 1的情况, 这个点就可以切换下一个点的先后手状态, 我们称这个点为转换点。
然后谁先到达转换点谁就胜利了, 因为无论下一个转换点或者是终点离现在这个转换点的 轮换次数 是奇数还是偶数,假设A到达了转换点 如果轮换次数是奇数, 那么A就可以将 a/b > 1的情况变成 a/b = 1(a=a%b+a), 那么下一个人没有操作空间, 然后因为接下来非转换点也没有操作空间, 那么就是根据轮换次数的奇偶确定到达下一个转换点的人, 那么A又可以到达转换点。
偶数的情况也是这样。
简单的来说,胜负的关键是转换点和终点, 然后 第一个转换点可以让到达的人到下一个胜负的关键点, 若不是终点, 那么又可以往下走到关键点, 直至终点。
代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define ULL unsigned LL 5 #define fi first 6 #define se second 7 #define lson l,m,rt<<1 8 #define rson m+1,r,rt<<1|1 9 #define max3(a,b,c) max(a,max(b,c)) 10 const int INF = 0x3f3f3f3f; 11 const LL mod = 1e9+7; 12 typedef pair<int,int> pll; 13 int cge; 14 int cal(int a, int b){ 15 int cnt = 0; 16 while(1){ 17 if(a < b) swap(a, b); 18 if(b == 0) return cnt; 19 cnt++; 20 if(a%b != 0 && a/b > 1 && cge == 0) cge = cnt&1 ? 1 : 2; 21 a %= b; 22 } 23 } 24 int main(){ 25 int a, b; 26 while(~scanf("%d%d", &a, &b) && a+b){ 27 cge = 0; 28 int cnt = cal(a, b); 29 if(cge == 0){ 30 if(cnt&1) puts("Stan wins"); 31 else puts("Ollie wins"); 32 } 33 else if(cge == 1) puts("Stan wins"); 34 else puts("Ollie wins"); 35 } 36 return 0; 37 }