1. 2029: [蓝桥杯2022初赛] 数的拆分

传送门：http://oj.ecustacm.cn/problem.php?id=2029

1.1. 题意

判断数字$a \le 10^{18}$能否表示成$x_1^{y_1}x_2^{y_2}$的形式，其中$x_1,x_2$为正整数，$y_1,y_2$为大于等于2的正整数。$T \le 100000$次询问。

1.2. Tag

数论

1.3. 难度

☆☆☆☆☆

1.4. 思路

首先考虑将$a$进行素因子分解$p_1^{q_1}p_2^{q_2}\cdot ...\cdot p_k^{q_k}$，首先要满足$q_i\ge 2$。

$\forall q_i \ge 2$，要拆分成$k_1*y_1+k_2*y_2=q_i$，$k_1,k_2 \ge 0,y_1,y_2\ge 2$。

$y_1=2,y_2=3$可以保证所有的$q_i \ge 2$均有非负整数解。

$2k_1+3k_2=k$对于$\forall k > 1$均有非负整数解：

1、$k\%3==0$：$k_1=0,k_2=\frac{k}{3}$

2、$k\%3==1$：$k_1=2,k_2=\frac{k-4}{3}$

3、$k\%3==2$：$k_1=1,k_2=\frac{k-2}{3}$

所以问题变成数字$a$能否变成$x_1^2x_2^3$。

对于$a=p_1^{q_1}p_2^{q_2}\cdot ...\cdot p_k^{q_k}$，只需要检测每个$q_i$是否大于等于$2$即可，只要大于等于$2$就可以按照对应的$k_1,k_2$分配到$x_1,x_2$里面。

由于$a\le 10^{18}$，所以$x_1^2x_2^3\le 10^{18}$。如果素因子$p>4000$，则$p^5\ge 10^{18}$。所以只需要暴力判断$4000$以内的素因子，对于大于$4000$的$p$，指数只可能是$2,3,4$，即判断一下是否为平方数或者立方数即可。

时间复杂度$O(T*550)$，$550$为$4000$以内素数数量。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
template <typename T>
inline T read(T& x) {
  x = 0;
  T w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x * w;
}
bool not_prime[4010];
int prime[4010], tot;
void init(int n)
{
    for(int i = 2; i <= n; i++)if(!not_prime[i])
    {
        prime[++tot] = i;
        for(int j = i + i; j <= n; j += i)
            not_prime[j] = 1;
    }
}
inline bool check(ll x)
{
    ///检查平方数
    ll y = pow(x, 0.5);
    if(y * y == x || (y + 1) * (y + 1) == x)
        return true;
    ///检查立方数
    y = pow(x, 1.0 / 3);
    if(y * y * y == x || (y + 1) * (y + 1) * (y + 1) == x || (y + 2) * (y + 2) * (y + 2) == x)
        return true;
    return false;
}
int main()
{
    init(4000);
    int T;
    read(T);
    while(T--)
    {
        ll x;
        read(x);
        if(check(x))
        {
            puts("yes");
            continue;
        }
        bool flag = true;
        for(int i = 1; i <= tot; i++)if(x % prime[i] == 0){
            int now = 0;
            while(x % prime[i] == 0)
            {
                now++;
                x /= prime[i] ;
            }
            ///cout<<prime[i]<<" "<<now<<endl;
            if(now == 1)
            {
                flag = false;
                break;
            }
        }
        if(check(x) & flag) {
            puts("yes");
            continue;
        }
        else
        {
            puts("no");
        }
    }
    return 0;
}