C. Product of Three Numbers

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given one integer number nn. Find three distinct integers a,b,ca,b,c such that 2≤a,b,c2≤a,b,c and a⋅b⋅c=na⋅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 tt independent test cases.

Input

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

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

Output

For each test case, print the answer on it. Print "NO" if it is impossible to represent nn as a⋅b⋅ca⋅b⋅c for some distinct integers a,b,ca,b,c such that 2≤a,b,c2≤a,b,c.

Otherwise, print "YES" and any possible such representation.

Example

input

Copy

5
64
32
97
2
12345

output

Copy

YES
2 4 8 
NO
NO
NO
YES
3 5 823 

C. Product of Three Numbers

题目链接：https://codeforces.com/contest/1294/problem/C

题意：

给你一个 n ，要求三个整数 a ，b ，c 使得 a * b * c = n 并且 a、b、c >= 2,且a、b、c不等

首先要有解，必要条件是n>=2*3*4=24;

其次不妨设

有，然后最小的a从2开始枚举，上界是，然后,继续根号枚举即可

#include<bits/stdc++.h>
#define ll long long
#define rg register ll
using namespace std;
ll n,t;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        if(n<24)
        {
            cout<<"NO"<<endl;
        }
        else
        {
            rg i,flag=0;
            for(i=2;i*i*i<=n;i++);
            for(rg i1=2;i1<=i;i1++)
            {
                ll k=n/i1;
                ll i2=sqrt(k);
                //cout<<i2<<" "<<i1<<" "<<k<<endl;
                //cout<<i1+1<<endl;;
                for(rg h=3;h<=i2;h++)
                {
                    ll i3=k/h;
                    //cout<<i3<<endl;
                    //cout<<i3<<" "<<i2<<" "<<h<<endl;
                    if(i3*i1*h==n&&h!=i1&&h!=i3&&i1!=i3)
                    {
                        cout<<"YES"<<endl<<i1<<" "<<h<<" "<<i3<<endl;
                        flag=1;
                        break;
                    }
                }
                if(flag)break;
            }
            if(!flag)cout<<"NO"<<endl;
        
        }
        
    }
    //while(1)getchar();
    return 0;
}

最后

以上就是优雅小霸王最近收集整理的关于Codeforces Round #615 (Div. 3)C. Product of Three NumbersC. Product of Three Numbers的全部内容，更多相关Codeforces内容请搜索靠谱客的其他文章。