C. Product of Three Numbers

time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given one integer number n. Find three distinct integers a,b,c such that 2≤a,b,c and a⋅b⋅c=n or say that it is impossible to do it.

If there are several answers, you can print any.

You have to answer t independent test cases.

Input
The first line of the input contains one integer t (1≤t≤100) — the number of test cases.

The next n lines describe test cases. The i-th test case is given on a new line as one integer n (2≤n≤109).

Output
For each test case, print the answer on it. Print “NO” if it is impossible to represent n as a⋅b⋅c for some distinct integers a,b,c such that 2≤a,b,c.

Otherwise, print “YES” and any possible such representation.

Example
inputCopy
5
64
32
97
2
12345
outputCopy
YES
2 4 8
NO
NO
NO
YES
3 5 823

题意：

给一个数n（n<=1e9）,如果能分解成abc==n（a，b，c>=2且不相等），输出YES，并且输出任意一个方案；反之输出NO；

思路：

三个不相同的数乘积为n,那么这三个数一定是n的因子；把n进行算数质因子分解，判断是否有三个不一样的因子；

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,int> mp;
ll pre[10010];
int main()
{int t;cin>>t;while(t--){mp.clear();//记得清空ll n;cin >>n;int cot=0;ll m=n;for(int i=2;i<=m/i;i++)//分解质因子并且记录每个质因子出现的次数{if(m%i==0) pre[cot++]=i;while(m%i==0){mp[i]++;m/=i;}}if(m>1) pre[cot++]=m,mp[m]++;if(cot==1)//当只有一个质因子的时候{if(mp[pre[0]]>=6){cout <<"YES"<<endl;printf("%lld %lld %lld\n",pre[0],pre[0]*pre[0],n/(pre[0]*pre[0]*pre[0]));//	cout <<mp[pre[0]]<<endl;}else cout <<"NO"<<endl;}else if(cot==2){if(mp[pre[0]]+mp[pre[1]]>=4){cout <<"YES"<<endl;printf("%lld %lld %lld\n",pre[0],pre[1],n/(pre[0]*pre[1]));}else cout <<"NO"<<endl;}else//如果有三个及以上的质因子存在那么就一定可以{cout <<"YES"<<endl;printf("%lld %lld %lld\n",pre[0],pre[1],n/(pre[0]*pre[1]));}}}