Tree Game [yukicoder No.726] - はまやんはまやんはまやん

考察過程

1. 一見難しそうな問題に見える
2. 勝敗判定系は手法がそんなに無いので1つ1つ考えていく
3. マンハッタン距離みたいな移動をするので、x,y座標は独立に扱えそう
4. 考察過程でこのような図が出てくる
5. Xについてその数以上の素数をxとすると、x - X - 1回移動できることがわかる
5. Yについても同様に言えて、移動可能回数は(x-X-1)+(y-Y-1)回であると言える
6. この偶奇で答えが求まりそう
7. あとは、色々コーナーケースがあるので注意

解法

https://yukicoder.me/submissions/280659

ゲームの勝敗判定系の中でも偶奇を使って求めていく。
cnt := 負け状態に至るまでに行える操作回数
その前にコーナーを処理しておこう。

XもYも素数ならば、どう移動しても負けるのでSecond勝利
XかYのどちらかが2であれば、2の座標をそのままにしても、3に移動させても素数なので、Second勝利
XかYのいずれかが素数ならば、素数の座標を最初に動かす必要があるので、cnt++

　
あとは、X,Yについてその数以上の素数をx,yとして、x,yを求める作業だが、Xから順にインクリメントしていって、素数か判定すればいい。
自分はミラーラビン素数判定法で素数判定をしたが、O(sqrt(10^9))の判定法でも間に合う気がする。
cnt += (x - X - 1) + (y - Y - 1)をして、cntが偶数ならsecondの勝利、奇数ならfirstの勝利とする。

ll Y, X;
//---------------------------------------------------------------------------------------------------
#define first "First"
#define second "Second"
string solve() {
    if (isprime(X) and isprime(Y)) return second;
    if (X == 2 or Y == 2) return second;

    ll cnt = 0;
    int rev = 0;
    if (isprime(X)) cnt++, X++;
    else if (isprime(Y)) cnt++, Y++;

    ll x = X, y = Y;
    while (!isprime(x)) x++;
    while (!isprime(y)) y++;

    cnt += (y - Y - 1) + (x - X - 1);
    if (cnt % 2 == 0) return second;
    return first;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> Y >> X;
    cout << solve() << endl;
}