【题意】：给出一个当前值q(q <= 10^13)，两个人轮流写出一个当前值的非平凡因子来取代当前值，谁不能写谁胜出。一个数的非平凡因子是指除1和本身之外的因子。两个人都采取最优决策，问最后谁胜出。

【题解】：博弈，直接记忆化搜索即可，只要搜到第一个必败态就可以跳出。
               利用map来处理可以把代码写得很短。

【代码】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define lc(x) (x << 1)
15 #define rc(x) (x << 1 | 1)
16 #define lowbit(x) (x & (-x))
17 #define ll long long
18 #define MAX 10000000
19 map<ll, bool> win;
20 map<ll, ll> ans;
21 ll q;
22 
23 bool dfs(ll x) {
24     if(win.find(x) == win.end()) {
25         bool isprime = true, WIN = false;
26         ans[x] = 0;
27         for(ll i = 2; i * i <= x && !WIN; i++) {
28             if(x % i == 0) {
29                 isprime = false;
30                 if(!dfs(i)) WIN = true, ans[x] = i;
31                 if(WIN) break;
32                 if(!dfs(x / i)) WIN = true, ans[x] = x / i;
33             }
34         }
35         win[x] = WIN || isprime;
36     } 
37     return win[x];
38 }
39 
40 int main() {
41     ans.clear(), win.clear();
42     while(cin >> q) {
43         if(dfs(q)) cout << 1 << endl << ans[q] << endl;
44         else cout << 2 << endl;
45     }
46     return 0;
47 }
48