大力 dp！

定义 $dp_{i,j}$ 表示拿到数对 $(i,j)$ 的最优操作，若是 $\texttt 0$ 表示必败。

显然初始状态有当 $i+j\ge n$ 时是必败的。

考虑倒着转移，对每个状态枚举三个后继状态，如果有一个是必败态那么就将当前 $dp$ 值设为这个操作的编号。

那么最终的答案就是 $dp_{x,y}$。

啊非常抱歉，可是 $n\le 30000$，前面那个做法根本过不了。

注意到 $x$ 可以表示成 $2^i3^j$ 的形式，考虑压缩状态，只记录指数就可以了。

于是就做完啦。

时间复杂度 $O(n\log^2 n)$。

#include<bits/stdc++.h>
int dp[30005][20][20];
int p2[20],p3[20];
extern "C" int _opt(int n, int x, int y){
    p2[0]=p3[0]=1;
    for(int i=1;i<=16;i++)p2[i]=p2[i-1]<<1;
    for(int i=1;i<=11;i++)p3[i]=p3[i-1]*3;
    for(int i=n;~i;i--)
    for(int j=15;~j;j--)
    for(int k=10;~k;k--){
        if(p2[j]*p3[k]+i>=n)dp[i][j][k]=0;
        else{
			if(!dp[i][j+1][k])dp[i][j][k]=2;
			else if(!dp[i][j][k+1])dp[i][j][k]=3;
			else if(!dp[i+p2[j]*p3[k]][0][0])dp[i][j][k]=1;
        }
    }
    if(x+y>=n)return 1;
    int pp2=0,pp3=0;
    while(x&&x%2==0)x>>=1,pp2++;
    while(x&&x%3==0)x/=3,pp3++;
    return dp[y][pp2][pp3];
}
//「是呀，没错（假声）。」
// 我动了动右手。

// 店内一阵骚动。
//「那是什么？」「演得好烂……」「根本就是假声嘛……」「声音有够假的……」「不对，等一下！她的嘴巴没有动耶！就这点来说很强了吧！」「可是还是假声啊。」「声音太高了，我听不清楚。」

// …………
// 我动了动右手。
//「简而言之，犯人就在这群人之中（假声）。」

//「烂死了……」「声音好假喔……」「咦，对不起。我完全听不懂。你刚才说什么？」

// …………
// 我默默摘下右手的布偶。