C. Product of Three Numbers
题意
给出一个数n问是否能将他拆成三个不同数的乘积 n小于1e9
由唯一分解定理得
a=(p1 ^ k1) × (p2 ^ k2) × (p3 ^ k3)…..
sqrt(n)内枚举可能的素因子 第三个数可有n/(p1*p2)得 若能得到三个因子且都不等于1那么有解
map容器的first是键值 second是映射值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
using namespace std;
typedef long long ll;
int main() {
int t;cin>>t;
while(t--){
int n;cin>>n;
map<int,int>ans;
for(int i=2;i*i<=n;i++){
if(n%i)continue;
ans[i]=1;n/=i;///得到的i一定是n的素因子
if(ans.size()==2)break;
}
//if(n!=1)ans[n]=1;
if(n!=1)ans[n]=1;
if(ans.size()<3)cout<<"NO"<<endl;
else {
cout<<"YES"<<endl;
for(auto i: ans)cout<<i.first<<" ";
cout<<endl;
}
}
}
|