## pF 採草莓

- **題目**
[TOJ 781](https://toj.tfcis.org/oj/contests/13/pro/781/)

- **By The Way**
:::warning
**這是一題賽局題**
**難度偏高，但是怕各位早早破台**
**所以就把這題也搬上來了**
:::

- **題解**
:::success
**這題的先備知識應該是大家國小、國中所耳熟能詳的 "輾轉相除法"**
**在這題，假如仔細看會發現有一種輾轉相除法的感覺**
**但是知道遊戲規則跟輾轉相除法有關係，又要怎麼解題呢?**
**我們可以稍微分析一下情況 :**
**當我們目前拿到了兩推數字為 ($N$, $M$)**
**而又假設 $N < M$ 則**
**我們可以很輕易的得知**
**接下的遊戲發展將會呈現三種狀態:**

* **假如 $N|M$ ($N$ 整除 $M$) 的話 $\to$ 目前先手必勝**
* **假如 $\lfloor \frac{M}{N} \rfloor = 1$ ($M$ 除以 $N$ 無條件捨去為 $1$) 時 $\to$ 則目前先手狀態必為下一個遊戲 ($N$, $M-N$) 的狀態的反面 (即 下局遊戲先手必勝則，目前先手必輸，反之則亦然)**
* **假如 $\lfloor \frac{M}{N} \rfloor > 1$ $\to$ 目前先手必勝**

**我們先來證明第一個局面 $N|M$ :**
**當 $N$ 整除 $M$ 時，很明顯先手只要拿 $M$ 株走**
**那麼先手必勝**

**那麼第二個呢局面呢? $\lfloor \frac{M}{N} \rfloor = 1$ :**
**當 $\lfloor \frac{M}{N} \rfloor = 1$ 時，很明顯**
**先手只能採取拿 $N$ 株的操作**
**不存在其餘選擇**
**則此狀況為中繼狀態，只能往下看下一個局面的結果**

**第三個局面就比較複雜一點了! $\lfloor \frac{M}{N} \rfloor > 1$ :**
**當 $\lfloor \frac{M}{N} \rfloor > 1$ 時，先手有兩種選擇**
* **一種是直接全部拿光，直接讓 $M$ 變為 $M%N$**
* **另一種選擇是使局面導向第二個局面 $\lfloor \frac{M}{N} \rfloor = 1$**

**但應該會有人好奇，為什麼沒有第三種情況，像是留 $2$ 的倍數 或其他的倍數?**
**因為留了其他倍數下來，就等同於留下了又一個這個狀態，看起來根本就沒用**
**那為什麼遇到這個情況肯定先手必勝呢？**
**我們可以試著把隨便一題的狀況列出來**
**11211212211121**
**基本上會看到只要沒有出現第一個情況(整除)的時候，那麼就是一個12陣列**
**而根據簡單的推論，可以發現遇到1的時候先手後手交換**
**遇到2的時候換到下一個數字可以是先手後手交換，也可以繼續是同一個先手後手**
**先手後手交換的情況就是全部拿光**
**先手後手不交換是，目前先手拿了很多，但只留下1在原地，那麼下一個先手也必須拿1**
**則至此先後手不換**

**了解以上規則後，我們來推論一下為什麼遇到2就必勝了:**
**首先，你會懷疑的是假如我第一個碰到2，但後面也有很多2**
**那麼我的決定是否會被下一個2的決定權擁有者給逆轉**
**這麼想其實是對的**
**但是可以想像到的，2跟2之間只會存在1或者根本沒有**
**而此中間的先後手交換順序是由奇偶數交換的**
**所以當我每一次碰到一個2時**
**我可以選擇將奇偶性倒轉，把局面導向 自己一定能拿到下個2，不然就是拿光**

**(這題很抽象，請仔細思考)**
:::

- **程式碼**

:::danger
**因為是OI賽制，所以會有子任務分數**
**出題者希望大家就算想不出來正解也能養成喇分數的習慣**
**子任務應該都出的很佛 (?**
**但個別子任務拿法都很諧咖就是了XD**
:::

:::spoiler **子任務一 (1/100)**

    #include <iostream>
    using namespace std;
    int main() {
        int a, b; cin >> a >> b;
        if((a == 13 && b == 10) || (a == 3 && b == 2)) cout << "Blame\n";
        else cout << "Bone\n";
    }

**(假如寫上面那樣應該會順便拿到子任務2 XD)**
:::

:::spoiler **子任務二 (14/100)**
**其實我們只要推斷出 $N|M$ 那個情況就可以過這個子任務了!**

    #include <iostream>
    using namespace std;
    int main() {
        cout << "Bone\n";
    }

****
:::

:::spoiler **子任務三、四 (48, 100/100)**
**三跟四只差在有沒有 long long 而已，問題不大**

    #include <iostream>
    using namespace std;
    int main() {
        long long a, b; cin >> a >> b;
        if(a > b) swap(a, b);
        bool bone = true;
        while(a != 1) {
            if(b%a==0 || b/a>1) break; // 此狀態必勝
            b %= a;
            swap(a, b);
            bone = !bone; // 轉換狀態
        }
        if(bone) cout << "Bone\n";
        else cout << "Blame\n";
    }

:::