操作を観察しなくとも、 grundy 数の定義に従ってメモ化再帰で mex を求めても高速です。
これは $1$ から $X$ までの約数の個数の総和が $O(X\log X)$ であることより分かります。

ボトルネックとなるのは \(1\) から \(X\) までの約数を求めることですが、これはエラトステネスの篩で前準備すると早いです。そうでなくとも、全て愚直に計算しても高速です。