素数+map BestCoder Round #54 (div.2) 1002 The Factor-白红宇

素数+map BestCoder Round #54 (div.2) 1002 The Factor

阅读量：5743 次

发布时间：2019-06-18

本文共 1526 字，大约阅读时间需要 5 分钟。

题意：给出一个数列，问数列的乘积的一个满足条件的最小因子是什么，没有输出-1。条件是不是素数

分析：官方题解：对于每一个数字，它有用的部分其实只有它的所有质因子（包括相等的）。求出所有数的所有质因子中最小的两个，相乘就是答案。如果所有数字的质因子个数不到两个，那么就是无解。时间复杂度

代码：

/************************************************* Author        :Running_Time* Created Time  :2015-9-5 19:48:28* File Name     :B.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 5e4 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;int a[110];map
                      
                        cnt;void factorize(int n) { for (int i=2; i*i<=n; ++i) { while (n % i == 0) { n /= i; cnt[i]++; } } if (n != 1) cnt[n]++;}int main(void) { int T; scanf ("%d", &T); while (T--) { cnt.clear (); int n; scanf ("%d", &n); for (int i=1; i<=n; ++i) { scanf ("%d", &a[i]); } for (int i=1; i<=n; ++i) { factorize (a[i]); } map
                       
                        ::iterator it; vector
                        
                          ans; for (it=cnt.begin (); it!=cnt.end (); ++it) { if (it->second) { for (int i=1; i<=it->second; ++i) { ans.push_back (it->first); if (ans.size () == 2) break; } } if (ans.size () == 2) break; } if (ans.size () != 2) puts ("-1"); else { printf ("%I64d\n", ans[0] * 1ll * ans[1]); } } return 0;}

转载于:https://www.cnblogs.com/Running-Time/p/4785381.html

你可能感兴趣的文章