Codeforces Round 107 (Div. 1) A. Win or Freeze （博弈论 + 数论*1400）

如果一个数是质数或者是1，那么一定是先手获胜，因为不能操作。

我们知道，一个数一定可以由 $p_1^{k_1}\ast p_2^{k_2}\ast p_3^{k_3}\dots$来唯一表示，那么我们就可以知道在一步之中一定可以实现将某一个数变为 $p_1\ast p_2$，后手必须除一次，然后先手无法操作，就取得了胜利。

以上是约数个数大于等于3的情况， 在其他的情况下就一定是后手获胜。

int q;cin >> q;if(q == 1 || check(q))cout << 1 << endl <<  0 << endl;else {int cnt = 0;vector<int>ans;for(int i = 2;i <= q/i;i++){while(q % i == 0){ans.push_back(i);q/=i;cnt++;}}if(q > 1)cnt++;if(cnt >= 3){cout << 1 << endl <<ans[0]*ans[1] << endl;}else cout << 2 << endl;}