백준 4342: 유클리드 게임 [C/C++]

https://www.acmicpc.net/problem/4342

4342번: 유클리드 게임

코드

 

 

 

#include <iostream>
#define endl    "\n"
#define ll  long long
static const auto fastio = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
 
using namespace std;
 
ll GCD(ll a, ll b){
    if (b == 0) return a;
    else return GCD(b, a % b);
}
 
ll EUC(ll A, ll B, ll c) {    
    ll a = A / GCD(A, B); ll b = B / GCD(A, B);
 
    if (a == 0 or b == 0) return c ^ 1;
    else {
        if (a < b * 2) return EUC((a - b < b ? b : a - b), (a - b < b ? a - b : b), c ^ 1);
        else {
            if (a % b != 0) {
                ll r = a % b;
                if (EUC((r < b ? b : r), (r < b ? r : b), c ^ 1) == c or 
                    EUC(r + b, b, c ^ 1) == c) 
                    return c;
                else return c ^ 1;
            }
            else return c;
        }
    }
}
int main() { 
    ll A, B;
    while (cin >> A >> B and !(A == 0 and B == 0)) {
        if (EUC((A < B ? B : A), (A < B ? A : B), 1)) cout << "A wins" << endl;
        else cout << "B wins" << endl;
    }
    return 0; 
} 
 

 

풀이

전제:

    A > B이다.

    n은 자연수이다.

 

1. (A, B)와 (A / gcd(A, B), B / gcd(A, B))는 같다.

문제 조건에 따라 다음 두 숫자는 B와 A - B * n 이다.

gcd로 나누어 진 수는 나누어 지기 전 수와 같은 비로 빼질 수 있기에 (A - B * n, B) == (A / gcd(A, B) - B / gcd(A, B) * n, B / gcd(A, B)) 이다.

이로서 시간 및 메모리를 줄일 수 있다.

 

이하 (A, B) == (A / gcd(A, B), B / gcd(A, B))라 서술한다.

 

2. (A, B)는 A >= B * 2 일 경우 그 차례의 사람이 반드시 승리한다.

A >= B * 2 일 경우, 이번 순서를 고르거나 다음 순서를 고를 수 있기에, 그 차례의 사람이 반드시 승리한다.

순서를 고를 수 있는 것은 A == B * (A / B) + A % B이기에  A = A % B 혹은 A = B + A % B를 만들 수 있기에,

 A = A % B로 이번 차례를 선택하던가, 상대방이 다음차례에 A -=B 를 할 수 밖에 없는 A = B + A % B로 선택할 수 있기 때문이다.