题目;题目链接
题目的意思是说:
两个人玩游戏,给出a和b,每次一个人都可以从大的数当中减去小的数的倍数。当一个人把某一个数变成1时,这个人就赢了。先手是Stan,问最后是谁赢了....
分析:
假设两个数为a,b(a>=b)
如果a==b.那么肯定是先手获胜。一步就可以减为0,b
如果a%b==0.就是a是b的倍数,那么也是先手获胜。
如果a>=2*b. 那么 那个人肯定知道a%b,b是必胜态还是必败态。如果是必败态,先手将a,b变成a%b,b,那么先手肯定赢。如果是必胜态,先手将a,b变成a%b+b,b.那么对手只有将这两个数变成a%b,b,先手获胜。
如果是b<a<2*b 那么只有一条路:变成a-b,b (这个时候0<a-b<b).这样一直下去看谁先面对上面的必胜状态。
这样的话就加判断a,b的关系...属于前3种就ok,否则就继续减,直到减成前三种情况就ok...代码:
#include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <cmath> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <stack> using namespace std; int min(int a, int b) { if(a<=b) return a; return b; } int max(int a, int b) { if(a>=b) return a; return b; } double min(double a, double b) { if(a<=b) return a; return b; } double max(double a, double b) { if(a>=b) return a; return b; } int main() { int m, n; while(cin >> m >>n) { if(!m && !n) break; int ans = 1; while(1) { if(m < n) swap(m, n); if(n == 0 || m == 0 || m%n == 0 || m/n >= 2) break; m = m%n; ans++; } if(ans % 2 == 1) printf("Stan wins\n"); else printf("Ollie wins\n"); } return 0; }
努力努力...