Subtask 1

手算打表有很難嗎？（WA 20%）

Subtask 1~2

考慮到以下幾點：

1. 一個人會贏若輪到他的時候 \(n\) 是質數
2. 因為輸入範圍的 prime gap 頗小，故不可能連續進行加 1 的操作太多次，也因此最大值不會大於初始的 \(n\) 太多
3. 令遊戲過程中 \(n\) 的最大值為 \(n_{max}\)，則在第 \(n_{max} + 1\) 回合根據鴿洞原理必定會走到之前走過的數字，也就是形成環，造成平手
4. 一個狀態必勝若且唯若其有至少一個必敗的後繼狀態；一個狀態必敗若且唯若其所有後繼均為必勝

因此可以寫出以 \(dp[回合數][目前的 n]\) 為狀態的 DP，時間 \(O(t + n^2)\)，空間 \(O(n^2)\) 或 \(O(n)\)（滾動）。（TLE/MLE 40%）

Subtask 1~3

觀察前面暴力解的結果，會發現除了 \(n \le 12\) 的渣渣，小愛會贏若且唯若 \(n\) 為質數，否則均為平手。

因此，只要特判 \(n \le 12\) 且暴力判 \(n\) 是否質數（枚舉 \(2 \sim [n^{1/2}]\) 看是否整除）即可，\(O(tn^{1/2})\)。（TLE 60%）

證明

顯然 \(n\) 為質數時先手必勝。以下證明 \(n \gt 12\) 且為合數時平手。

稱一個數 \(n\) 為必勝點，如果 \(n\) 使先手必勝； 稱一個數 \(n\) 為必敗點，如果 \(n\) 使先手必敗。

記 \(p(n)\)表示 \(n\)最小的質因數。

Lemma：\(n\) 是必勝點若且唯若 \(\frac{n}{p(n)}\) 是必敗點

pf:考慮 \(n\) 是必勝點，反設 \(\frac{n}{p(n)}\) 不是必敗點。

三種操作中，先手只能選擇會到達必敗點的操作，所以一定不會選擇操作3(由假設)。

然而，無論先手選擇操作1或2，後手都能選擇另一個將數字變換回 \(n\) ，從而無窮進行下去，是平手，與已知矛盾，得證。

Corollary：\(n\) 是必敗點若且唯若 \(\frac{n}{p(n)}\)是必勝點，\(\frac{n+1}{p(n+1)}\)、\(\frac{n-1}{p(n-1)}\) 是必敗點

pf: 因為如果 \(n\) 要是必敗點，那 \(\frac{n}{p(n)}\)、\(n+1\)、\(n-1\) 都要是必勝點。

因此，首先以上面的dp驗證 \(n\leq144\) 的狀況，已知 \(n\leq144\) 假設成立。

採強數學歸納法，假設對於所有 \(k<n\) 假設成立。

對於 \(n\geq145\)，\(\frac{n}{p(n)} \geq n^{1/2} > 12\)，所以一定不是必敗點或必勝點。

由上面的討論知， \(n\) 也不可能是必勝或必敗點，得證。

Subtask 1~2, 4

Solution 1

試著唬爛地把 subtask 1 \(\sim\) 2 的解之回合數上限調低到一個常數（例如 10），然後你就會發現你過了 subtask 4。證明可由上述 subtask 1 \(\sim\) 3 的結論得知，時間 \(O(t + n)\)，空間 \(O(n)\)。（TLE/MLE 60%）

Solution 2

觀察輸入範圍的 prime gap，可以發現對任意 \(n\)，\(n\) 和 \(2n\) 之間必定存在質數。換句話說，構成平手的環中一定只存在加減兩個操作。又，加減構成的環必定存在「加緊接著減」和「減緊接著加」。因此，可以令 DP 狀態為 \(dp[前次操作種類][目前的 n]\)，時間 \(O(t + n)\)，空間 \(O(n)\)。（TLE/MLE 60%）

Solution 3

接續 subtask 1 \(\sim\) 3，用質數篩預處理質數列表，就可以 \(O(lgn)\) 判斷質數，整體時間 \(O(nlgn + tlgn)\) 或 \(O(n + tlgn)\)（線性篩），空間 \(O(n)\)。（TLE/MLE 60%）

Subtask 1~4

如果只想到上面證明的Lemma和Corollary，可以直接記憶化搜索dp。

記憶化搜索dp是指在dfs求值時，紀錄所有計算過的dp值，遇到算過的直接取值(以map,unordered_map或cc_hash_table等容器存取)。

或是結合dfs和dp，對小的值(\(10^6\))以下dp，一旦dfs到\(10^6\)就回傳dp值。(TLE/MLE 80%)

理論上應該是要這樣子的啦，但是實際上直接dfs就能過了(TLE/MLE 80%)。

常數小一點或是剪枝的話甚至有可能AC，一個最合理的剪枝是判掉質數。

Subtask 1~5

Solution 1

用 Miller-Rabin 判質數，\(O(tlgn)\)。（AC 100%）

Solution 2

C/C++ 的 GMP 和 Java 的 BigInteger 都有快速判質數的函數，內部大多是使用 Miller-Rabin 或是費馬小定理。（AC 100%）

不過，大多數的比賽不會提供 GMP，也不一定能使用 Java，所以建議還是學一下 Miller-Rabin。

標程

C++ Miller-Rabin（by tan7680）

#include<bits/stdc++.h>
using namespace std;
long long pwr(long long a,long long n,long long M)
{
    if(n==0)return 1;
    long long ans=pwr(a,n/2,M);
    ans=(ans*ans)%M;
    if(n&1)return (ans*a)%M;
    return ans;
}
bool prime(long long x)
{
    if(x==2)return 1;
    int t[3]={2,7,61};
    int u=x-1,c=0;
    while(u%2==0){u/=2;c++;}
    for(int l=0;l<3;l++)
    {
        int a=t[l]%x;
        if(a==0||a==1||a==x-1)continue;
        long long w=pwr(a,u,x);
        if(w==1||w==x-1)continue;
        for(int i=1;i<c;i++)
        {
            w=(w*w)%x;
            if(w==1)return 0;
            if(w==x-1)break;
        }
        if(w!=x-1)return 0;
    }
    return 1;
}
int main()
{
    cin.tie(0);ios_base::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        if(n==4||n==6||n==8||n==12){cout<<"Ai"<<'\n';continue;}
        if(prime(n))cout<<"Ai"<<'\n';
        else cout<<"Draw"<<'\n';
    }
return 0;
}

Scala BigInt（by WillyPillow）

object x003 extends App {
  for (n <- io.Source.stdin.getLines.drop(1).map(_.toInt)) {
    if (n == 4 || n == 6 || n == 8 || n == 12 || BigInt(n).isProbablePrime(8))
      println("Ai")
    else
      println("Draw")
  }
}