【题目描述】
给定 T 个正整数 ，分别问每个
能否表示为
的形式，其中
,
为正整数，
,
为大于等于 2 的正整数。
【输入格式】
输入第一行包含一个整数 T 表示询问次数。
接下来 T 行，每行包含一个正整数 。
【输出格式】
对于每次询问, 如果 能够表示为题目描述的形式则输出
yes，否则输出 no。
【数据范围】
对于 10% 的评测用例，1 ≤ T ≤ 200， ≤
；
对于 30% 的评测用例，1 ≤ T ≤ 300， ≤
；
对于 60% 的评测用例，1 ≤ T ≤ 10000，≤
；
对于所有评测用例，1 ≤ T ≤ 100000，1 ≤ ≤
。
【输入样例】
7
2
6
12
4
8
24
72
【输出样例】
no
no
no
yes
yes
no
yes
【样例解释】
【思路】
题解来源：AcWing 4650. 数的拆分 - AcWing
【代码】
#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;elsel = 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;elsel = 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';elsestd::cout << "no" << '\n';}
}
