| 
Nvodskは寒いので、直前に書いた整数の自明でない約数を１つ紙に書いてその回数だけホテルの周りを走るゲームをするｗ
（ロシア企業(?)運営のサイトらしくていい）
約数を書けなくなった方が勝ち。最初に q ( <= 10**13) が書いてあって二人が最適なゲームをする場合、どっちが勝つか、最初(1)が勝つなら初手も出力する。
n が Win number か Lose number か計算する関数 f を書いた。
をメモ化再帰で。そしたら TLE になった。
（後ほど）
１つでも Lose があったら f(n)==Win に決定するのでそこで抜けて良いのに抜けてなかった。そこを抜けるようにしたら accepted.
しかし正解者のコードを見てるとみなさん再帰させてない。
この問題の場合はもっと簡単なロジックで答えがでるらしい。今のところ理解できず。
あと、こういう約数とか素数とかからむとオーダーがよくわからなくなる。
メモ化のキーの範囲は long long だけどうまく重複するので大丈夫とか、そのへん。
map<ll, int> memo; ll move=0; int f(ll n) { if(memo.count(n)) return memo[n]; int allW=1; int win = 1; for(ll i=2;i*i<=n;i++) { if(n % i == 0) { int r0=f(i); int r1=f(n/i); allW &= r0; allW &= r1; if(!r0) move=i; if(!r1) move=n/i; win=0; if(!r0||!r1) return memo[n] = 1; //// ここ入れたら accepted } } int ret = win ? win : (allW ? 0 : 1); //cout<<n<<" "<<ret<<endl; return memo[n] = ret; } int main() { ll q; cin>>q; int r = f(q); cout<<(r?1:2)<<endl; if(r) cout<<move<<endl; return 0; }
