1. 2029: [蓝桥杯2022初赛] 数的拆分
传送门:http://oj.ecustacm.cn/problem.php?id=2029
1.1. 题意
判断数字能否表示成的形式,其中为正整数,为大于等于2的正整数。次询问。
1.2. Tag
数论
1.3. 难度
☆☆☆☆☆
1.4. 思路
首先考虑将进行素因子分解,首先要满足。
,要拆分成,。
可以保证所有的均有非负整数解。
对于均有非负整数解:
1、:
2、:
3、:
所以问题变成数字能否变成。
对于,只需要检测每个是否大于等于即可,只要大于等于就可以按照对应的分配到里面。
由于,所以。如果素因子,则。所以只需要暴力判断以内的素因子,对于大于的,指数只可能是,即判断一下是否为平方数或者立方数即可。
时间复杂度,为以内素数数量。
#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;
}