Win or Freeze

题解

• 如果输入的数为一个质数，那么玩家做不出任何操作，所以这种情况是必赢的。
• 如果输入的数有两个质因数，且每个质因数都只出现了一次，两个质数分别为 $p_1, \ p_2$，则无论除以 $p_1$ 还是 $p_2$，得到的数都是质数，即第一种情况，所以这种情况是必输的。
• 如果输入的数有一个质因数，且这个质因数出现了两次，这个质数为 $p_1$，则只能除以 $p_1$，得到的数为 $p_1$，是个质数，即第一种情况，所以这种情况是必输的。
• 其他情况，则有 $k_1 + k_2 + k_3 + \dots + k_n > 2$，可以通过除以一个数使得 $k_1 + k_2 + k_3 + \dots + k_n = 2$ 是可行的，即第二种情况或第三种情况，所以这种情况是必赢的的。

• 如果输入的数为质数时，玩家 $1$ 刚开局就会赢，不用做操作。
• 如果输入的数为有两个质因数，且每个质因数都只出现了一次，那么玩家 $2$ 必赢。
• 如果输入的数为有一个质因数，且质因数出现了两次，那么玩家 $2$ 必赢。
• 其他情况，玩家 $1$ 必赢，除以的数只要使得操作后的数的 $k_1 + k_2 + k_3 + \dots + k_n = 2$ 就行了。

• 如果这个数的 $k_1 + k_2 + k_3 + \dots + k_n$ 满足 $k_1 + k_2 + k_3 + \dots + k_n = 1$ 或 $k_1 + k_2 + k_3 + \dots + k_n \ge 3$，玩家 $1$ 必胜，操作方案是好构造的。
• 如果这个数的 $k_1 + k_2 + k_3 + \dots + k_n$ 满足 $k_1 + k_2 + k_3 + \dots + k_n = 2$，玩家 $2$ 必胜。

代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define dbg(x) cout << #x " = " << (x) << endl
#define quickio ios::sync_with_stdio(false);
#define quickin cin.tie(0);
#define quickout cout.tie(0);

using namespace std;

signed main() {
    quickio
    quickin
    quickout
    int n; cin >> n;
    int tot = 0, m = n;
    vector <int> vec;
    if(n == 1) tot = 1;
    for(int i = 2; i * i <= n; i++)
        while(n % i == 0) tot++, n /= i, vec.push_back(i);
    if(n > 1) vec.push_back(n), n = 1, tot++;
    if(tot == 1) cout << 1 << endl << 0 << endl;
    else if(tot == 2) cout << 2 << endl;
    else cout << 1 << endl << vec[0] * vec[1] << endl;
    return 0;
}