第十三届蓝桥杯省赛A组题解传送门

题目大意

给定$T$个正整数$n$，分别问每个$n$能否表示为$x_1^{y_1}\times x_2^{y_2}$的形式
其中$x_1,x_2$为正整数，$y_1,y_2$ 为大于等于$2$的正整数

解题思路

完全没有数论基础的话可以先看看质数专题和约数专题
由算数基本定理知任何一个大于$1$的正整数都能唯一分解成有限个质数的乘积，
即$N={p_1}^{c_1}{p_2}^{c_2}\cdots {p_m}^{c_m}$
首先先明确，如果存在一个$c_i=1$，那么一定是$no$
这是显然的，否则$y_1,y_2$ 不可能为大于等于$2$的正整数
那么就是对于每一个质因数的指数$c_i(c_i\geq 2)$
我们要解一个这样的方程：$c_i=k_1\times y_1+k_2\times y_2$，其中$k_1,k_2$为非负整数，$y_1,y_2\geq 2$
观察样例，可以推测$y_1=2,y_2=3$时一定有非负整数解
然后我们试着证明：
$2\times k_1+3\times k_2=k,k\geq 2$
当$k\equiv 0\pmod 3$时,$k_1=0,k_2=\frac{k}{3}$
当$k\equiv 1\pmod 3$时,$k_1=2,k_2=\frac{k-4}{3}$
当$k\equiv 2\pmod 3$时,$k_1=1,k_2=\frac{k-2}{3}$
证毕，发现推测是对的
所以问题转变成，$x$能否表示成$x_1^{2}\times x_2^{3}$的形式
当$x_1$是$1$时，检查是否是立方数即可
当$x_2$是$1$时，检查是否是平方数即可
然后现在解决当$x_1$和$x_2$都不是$1$时的情况
若能拆解，则$x=x_1^{2}\times x_2^{3}$
则$x\geq min(x_1,x_2)^5$，即$min(x_1,x_2)\leq x^{\frac{1}{5}}$
$x$最大是$10^{18}$,开五次根号后不超过$4000$
就是说，对于超过$4000$的$x$的质因数$p_i$，它的指数$c_i$一定不超过$5$(如果超过了那直接比$x$都大了)
那么我们先线性筛处理出来不超过$4000$的质数
然后把其中是$x$的因数的除掉
过程中间如果发现一个$c_i=1$，直接可以知道是$no$(不要忘记刚开始的这个结论)
如果整个过程顺利地完成了，此时$x$可能还剩下由大于$4000$的质因数构成的数
那么我们利用这些质数的指数一定不超过$5$且不能是$1$的这两个结论，知道指数一定是$2,3,4$
也就是说，剩下的$x$，一定还是要么平方数要么立方数
那么就再$check$一次即可

具体代码

#include <bits/stdc++.h>
typedef long long LL;
const int N = 4010;
int v[N]; // v[i]记录数字i的最小质因子
int prime[N], m;
void init() //线性筛
{
    memset(v, 0, sizeof v); // v[i]记录数字i的最小质因子
    m = 0;                  // m记录质数个数
    for (int i = 2; i <= 4000; ++i)
    {
        if (v[i] == 0) // i是质数
        {
            v[i] = i;
            prime[++m] = i;
        }
        for (int j = 1; j <= m; ++j)
        {
            //若i有比prime[j]更小的质因子，或超出n的范围，则停止循环
            if (prime[j] > v[i] || prime[j] > 4000 / i)
                break;
            // prime[j]是合数i*prime[j]的最小质因子
            v[i * prime[j]] = prime[j];
        }
    }
}
bool check(LL x) //判断一个数是否是平方数或立方数
{
    LL l = 1, r = 2e9;
    while (l < r)
    {
        LL mid = l + r >> 1;
        if (mid * mid >= x)
            r = mid;
        else
            l = mid + 1;
    }
    if (l * l == x)
        return true;
    l = 1, r = 2e6;
    while (l < r)
    {
        LL mid = l + r >> 1;
        if (mid * mid * mid >= x)
            r = mid;
        else
            l = mid + 1;
    }
    if (l * l * l == x)
        return true;
    return false;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    std::cin >> T;
    init();
    while (T--)
    {
        LL x;
        std::cin >> x;
        if (check(x))
        {
            std::cout << "yes" << '\n';
            continue;
        }
        bool impossible = false;
        for (int i = 1; i <= m; ++i)
        {
            if (x % prime[i] == 0)
            {
                int t = 0;
                while (x % prime[i] == 0)
                {
                    ++t;
                    x /= prime[i];
                }
                if (t == 1)
                {
                    impossible = true;
                    break;
                }
            }
        }
        if (!impossible && check(x))
            std::cout << "yes" << '\n';
        else
            std::cout << "no" << '\n';
    }
}