问题描述
给定 �T 个正整数 ��ai, 分别问每个 ��ai 能否表示为 �1�1⋅�2�2x1y1⋅x2y2 的形式, 其中 �1,�2x1,x2 为正整数, �1,�2y1,y2 为大于等于 2 的正整数。
输入格式
输入第一行包含一个整数 �T 表示洵间次数。
接下来 �T 行, 每行包含一个正整数 ��ai 。
输出格式
对于每次询问, 如果 ��ai 能够表示为题目描述的形式则输出 yes, 否则输出 no.
样例输入
7
2
6
12
4
8
24
72
样例输出
no
no
no
yes
yes
no
yes
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e5 + 10; 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 square_number(ll x) { ll y = sqrt(x); while(y * y <= x)//开平方存在精度误差,需要多判断几步 { if(y * y == x)return true; y += 1; } return false; } //判断立方数 inline bool cubic_number(ll x) { ll y = pow(x, 1.0 / 3); while(y * y * y <= x)//开立方存在精度误差,需要多判断几步 { if(y * y * y == x)return true; y += 1; } return false; } int main() { //预处理4000以内的素数 init(4000); int T; cin >> T; while(T--) { ll a; cin >> a; //先特判平方数、立方数 if(square_number(a) || cubic_number(a)) { cout<<"yes"<<endl; continue; } bool flag = true; for(int i = 1; i <= tot; i++)if(a % prime[i] == 0) { int mi = 0; while(a % prime[i] == 0)a /= prime[i], mi++; //幂次必须大于1 if(mi == 1){flag = false; break;} } //剩余的部分再次判断平方数和立方数 if(flag && (square_number(a) || cubic_number(a))) cout<<"yes"<<endl; else cout<<"no"<<endl; } return 0; }
标签:输出,正整数,no,ai,int,拆解,yes
From: https://www.cnblogs.com/weinan030416/p/17113624.html