「QFOI R2」树色尤含残雨 官方题解

· · 题解

考查内容：

设 x 的唯一分解为 \prod_{i=1}^mp_i^{\alpha_i}，也就是说 x 可以被划分为 m 个质数的若干次幂的乘积。

当 x 为一个质数的正整数次幂时，无法进行任何操作，因此答案为 x。

当 x 为“无平方因子数”（Square-Free Number）时，一次操作只能消除掉 x 的两个不同质因子。若 2\mid m，此时 x 可以变成 1；若 2\nmid m，此时必定剩下一个质因数无法被消除，取最小的质因数即可。

否则，答案一定为 1。这是由于若 2\mid m，每次消除两个不同质因子即可；若 2\nmid m，可以将一个 \alpha_i\ge 2 对应的 p_i 拆分到两次操作中，转化为 2\mid m 的情况。

int x, y;
cin >> x; y = x;
vector<tuple<int, int>> div;
bool squarefree = true;
for(int i = 2; i * i <= x; ++i) {
    if(x % i == 0) {
        int cnt = 0;
        for(; x % i == 0; x /= i) ++cnt;
        div.emplace_back(i, cnt);
        if(cnt >= 2) squarefree = false;
    }
}
if(x > 1) div.emplace_back(x, 1);
if((int)div.size() == 1) cout << y << endl;
else if(squarefree) {
    if((int)div.size() & 1) cout << get<0>(div[0]) << endl;
    else cout << 1 << endl;
}
else cout << 1 << endl;