UVA10622 完全P次方数 Perfect P-th Powers 题解

第一次写一道被恶意评分的紫题的题解QWQ

看上去本题远没有紫题这么难，对 $n$ 质因数分解再输出每个质因数的指数的最大公因数就行了。但是本题有几个坑：

1. 说明一点，本题 $x$ 为 $int$ 范围内的数， $b$ 也是的，而 $int$ 范围内包含负数！

2. 若 $x$ 为负数且能写成 $b^p$ 的形式，那么 $b$ 也为负数且 $p$ 为奇数，否则 $b^p$ 为非负数。

所以对于 $x$ 为负数的情况，只能先将 $x$ 转为正数，再分解质因数。对于最终的结果，如果它是偶数，就要不断地将它除以 $2$ （相当于底数乘 $2$ ，指数除以 $2$）。但是你以为没了吗？

3. 对 $n$ 取相反数后，此时 $n$ 有范围吗，应当怎么办？

代码很简单：

#include <cstdio>
#include <vector>
int gcd(int a, int b) {
    return !b ? a : gcd(b, a % b);
}
std::vector<int> a;//a为每个n质因数的指数
void fj(long long &n) {
    bool minus = 0;//n是否为负数
    if (n < 0)
        minus = 1, n = -n;
    a.clear();//多组数据，需要清空
    for (long long i = 2; i * i <= n; i++)
        if (!(n % i)) {
            a.resize(a.size() + 1);//先调长度
            a[a.size() - 1] = 0;//最好置0
            while (!(n % i))
                ++a[a.size() - 1], n /= i;
        }
    if (n > 1)
        a.push_back(1);
    int g = a[0];
    for (int i = 0; i < a.size(); i++)
        g = gcd(g, a[i]);//算出最终结果
    if (minus)
        while (!(g & 1))
            g >>= 1;//意义见上
    printf("%d\n", g);
}
int main() {
    long long n;
    while (scanf("%lld", &n) != EOF) {
        if (!n)
            break;
        if (n == 1)
            puts("。。。");
            //原题中没有n=1的情况，随便输出什么都行
        else
            fj(n);
    }
    return 0;
}

大概算的上绿题吧（主要是陷阱太多了）