hdu 5428 质因子

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

问题描述
有一个数列，FancyCoder沉迷于研究这个数列的乘积相关问题，但是它们的乘积往往非常大。幸运的是，FancyCoder只需要找到这个巨大乘积的最小的满足如下规则的因子：这个因子包含大于两个因子（包括它本身；比如，4有3个因子，因此它是满足这个要求的一个数）。你需要找到这个数字并输出它。但是我们知道，对于某些数可能没有这样的因子；在这样的情况下，请输出-1.

这个因子包含大于两个因子
也就是说必须包含三个因子可以为本身
求出所有数的所有质因子中最小的两个，相乘就是答案。
如果所有数字的质因子个数不到两个，那么就是无解

输入样例
2
3
1 2 3
5
6 6 6 6 6
输出样例
6
4

 # include <iostream>

 # include <cstdio>

 # include <cstring>

 # include <algorithm>

 # include <string>

 # include <cmath>

 # include <queue>

 # define LL long long

 using namespace std ;

 LL a[] ;

 LL vis[] ;

 int main ()

 {

     //freopen("in.txt","r",stdin) ;

     int T ;

     cin>>T ;

     while(T--)

     {

         int n , i ;

         int cnt =  ;

         cin>>n ;

         for (i =  ; i < n ; i++)

             cin>>a[i] ;

         memset(vis ,  , sizeof(vis)) ;

         for (i =  ; i < n ; i++)

         {

             LL x = a[i] ;

             for (LL j =  ; j*j <= x ; j++)

             {

                 while(x%j==)

                 {

                     vis[cnt++] = j ;

                     x /= j ;

                 }

             }

             if (x > )

                 vis[cnt++] = x ;

         }

         sort(vis , vis+cnt) ;

         if (cnt < )

             cout<<-<<endl ;

         else

             cout<<vis[]*vis[]<<endl ;

     }

     return  ;

 }