Mô tả bài toán

Hai hậu duệ của Euclid, Stan và Ollie, đang chơi một trò chơi số học cổ truyền. Cho hai số nguyên dương \(M\) và \(N\). Trò chơi được thực hiện theo lượt, bắt đầu với Stan, với các bước như sau:

• Ở lượt của người chơi, ta lấy số lớn hơn trong cặp \((a, b)\) và trừ đi bội số nguyên dương của số nhỏ hơn sao cho kết quả không âm.
• Sau đó, lượt chơi chuyển sang đối thủ với cặp số mới gồm số vừa tính được và số nhỏ hơn ban đầu.
• Trò chơi kết thúc khi một trong hai số trở thành 0; người chơi làm cho một trong số trở thành 0 sẽ thắng.

Nhiệm vụ là xác định, nếu cả hai người chơi đều chơi tối ưu, ai sẽ là người chiến thắng.

Ý tưởng giải

Bài toán có mối liên hệ rất chặt chẽ với thuật toán Euclid dùng để tìm ước số chung lớn nhất (GCD). Ở mỗi bước của thuật toán Euclid, ta thực hiện các phép trừ (hoặc phép chia lấy phần nguyên) tương tự như các nước đi trong trò chơi. Dựa vào đó, ta có thể xây dựng một hàm đệ quy xác định chiến thắng như sau:

1. Sắp xếp cặp số:
   Cho hai số \(a\) và \(b\) với \(a \ge b\).

2. Điều kiện thắng ngay:
   Nếu:

   • \(b = 0\) (trường hợp kết thúc trò chơi),
   • hoặc \(a\) chia hết cho \(b\) (tức \(a \% b = 0\)),
   • hoặc \(a / b \ge 2\) (nghĩa là người chơi hiện tại có thể trừ một bội số đủ lớn của \(b\) để làm giảm \(a\) xuống còn giá trị không cho đối thủ cơ hội chiến thắng),

   thì người chơi hiện tại có thể thắng ngay.

3. Đệ quy và đảo ngược kết quả:
   Nếu không thoả một trong những điều kiện trên, người chơi hiện tại thực hiện nước đi: trừ \(b\) khỏi \(a\) (tương đương với lấy \(a - b\)), và chuyển lượt cho đối thủ với cặp số mới \((b, a - b)\). Kết quả của nước đi này sẽ được đảo ngược (với giả thiết đối thủ cũng chơi hoàn hảo).

Như vậy, ta định nghĩa hàm euclidGame(a, b) trả về true nếu người chơi hiện tại (với cặp số \((a, b)\)) có chiến lược thắng và false nếu không.

Ví dụ minh họa

Lấy cặp số \((25, 7)\) làm ví dụ:

1. Lượt 1 (Stan):

   • Sắp xếp: \(a = 25\), \(b = 7\).
   • \(25 / 7 = 3 \geq 2\), nên Stan có thể trừ \(7 \times 2 = 14\) từ 25 được 11.
   • Trạng thái mới: \((11, 7)\).

2. Lượt 2 (Ollie):

   • Sắp xếp: \(a = 11\), \(b = 7\).
   • \(11 / 7 = 1\) không thoả điều kiện thắng ngay, nên Ollie trừ \(7\) từ 11 được \(4\).
   • Trạng thái mới: \((7, 4)\) (sau sắp xếp lại: \(a = 7\), \(b = 4\)).

3. Lượt 3 (Stan):

   • Với cặp \((7, 4)\): \(7 / 4 = 1\) không đủ để thắng ngay, nên Stan trừ \(4\) từ \(7\) được \(3\).
   • Trạng thái mới: \((4, 3)\).

4. Lượt 4 (Ollie):

   • Với cặp \((4, 3)\): \(4 / 3 = 1\) không thoả điều kiện, nên Ollie trừ \(3\) từ \(4\) được \(1\).
   • Trạng thái mới: \((3, 1)\) (sắp xếp lại: \(a = 3\), \(b = 1\)).

5. Lượt 5 (Stan):

   • Với cặp \((3, 1)\): \(3 / 1 = 3 \ge 2\), Stan có thể thắng ngay bằng cách trừ \(1 \times 3 = 3\) từ 3, khiến số kia trở thành 0.
   • Kết quả: Stan thắng.

Phân tích độ phức tạp

• Ở mỗi bước, số lớn \(a\) giảm đi ít nhất bằng \(b\) và đôi khi giảm mạnh nếu \(a / b \geq 2\).
• Thuật toán Euclid cổ điển có độ phức tạp trung bình là \(O(\log(\min(M, N)))\).
• Ở đây, số bước (số lần gọi đệ quy) cũng tương tự, do đó độ phức tạp của giải thuật là \(O(\log(\min(M, N)))\).
• Với số bộ test \(C \le 6\) và các số ban đầu \(M, N < 2^{31}\), giải thuật chạy rất nhanh và hiệu quả.

Code minh họa

Dưới đây là code C++ sử dụng kiểu long long để giải quyết bài toán:

#include <iostream>
#include <algorithm>
using namespace std;

// Hàm đệ quy xác định chiến thắng của người chơi hiện tại.
// Trả về true nếu người chơi hiện tại có chiến lược thắng, false nếu không.
bool euclidGame(long long a, long long b) {
    if(a < b) swap(a, b);
    // Nếu số nhỏ bằng 0, hoặc nếu a chia hết cho b hoặc nếu a / b >= 2,
    // thì người chơi hiện tại có thể thắng ngay.
    if(b == 0 || a % b == 0 || a / b >= 2)
        return true;
    // Nếu không, chuyển sang trạng thái mới (b, a - b) và đảo ngược kết quả.
    return !euclidGame(b, a - b);
}

int main(){
    int C;
    cin >> C;
    while(C--){
        long long M, N;
        cin >> M >> N;
        if(euclidGame(M, N))
            cout << "Stan wins" << "\n";
        else
            cout << "Ollie wins" << "\n";
    }
    return 0;
}