自动搬运

查看原文

来自洛谷，原作者为

	rui_er 九万里风鹏正举

搬运于2025-08-24 22:57:43，当前版本为作者最后更新于2024-04-05 16:00:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考查内容：

• 【3】整数唯一分解定理。
• 【3】贪心法。

设 $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;