Euclid‘s Game(博弈)

发布于 2020-10-29  0 次阅读


减去两数差值的Euclid’s Game

题目大意:

A和B比赛,玩家必须在棋盘上写上一个正数,该数字等于棋盘上已有的两个数字的差值;
这个数字必须是新的,即与主板上已有的所有数字不同。无法移动的玩家输掉游戏。
A先手

思路:

判断较大值除以两数的最大公约数的奇偶性即可

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
inline int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}
void solve(){
    int n, m;
    while(~scanf("%d%d", &n, &m) && n && m){
        if(n<m) swap(n,m);
        if((n/gcd(n,m))&1)  cout<<"Stan wins"<<endl;
        else                cout<<"Ollie wins"<<endl;
    }
	return ;
}

signed main(){
    solve();
    return 0;
}

减去两数倍数的Euclid’s Game

题目大意:

Euclid's Game
Stan wins和Stan wins进行比赛,给定两个数,每次将两个数中较大的那个减去较小的那个数的整数倍,减去后依然为正整数
直到两个数有一个数为0,先到0的胜利。
Stan wins先手

思路:

第一次遇见可以选择的人将获胜
即为当a ≥ 2 ∗ b的时候,可以选择转移到( a % b , b ) 或者( a % b + b , b ) 从而产生不同的局势,而这个人足够聪明所以他可以判断出必胜态所以我们需要找到面临情况这个的人

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
inline int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}
void solve(){
    int n, m;
    while(~scanf("%d%d", &n, &m) && (n||m)){
        if(n<m) swap(n,m);
        int flag=1;
        while(1){
            if(n%m==0||m==0||n>=2*m) break;
            int t=n;
            n=m;
            m=t-m;
            flag^=1;
        }
        if(flag)    cout<<"Stan wins"<<endl;
        else        cout<<"Ollie wins"<<endl;
    }
	return ;
}

signed main(){
    solve();
    return 0;
}

平平无奇的大学在读本科生