Win or Freeze

hjm777 · 2025-01-02 11:31:50 · 题解

题解

不妨假设输入的数为 q = p_1^{k_1} \times p_2^{k_2} \times p_3^{k_3} \times \dots \times p_n^{k_n}。

我们讨论输入的数：

• 如果输入的数为一个质数，那么玩家做不出任何操作，所以这种情况是必赢的。

• 如果输入的数有两个质因数，且每个质因数都只出现了一次，两个质数分别为 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;
}