题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5428

The Factor

Accepts: 101

Submissions: 811

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

问题描述

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

输入描述

输入文件的第一行有一个正整数T \ (1 \le T \le 15)T (1≤T≤15)，表示数据组数。

接下去有TT组数据，每组数据的第一行有一个正整数n \ (1 \le n \le 100)n (1≤n≤100).

第二行有nn个正整数a_1, \ldots, a_n \ (1 \le a_1, \ldots ,a_n \le 2\times 10^9)a1,…,an (1≤a1,…,an≤2×109), 表示这个数列。

输出描述

输出TT行TT个数表示每次询问的答案。

输入样例

输出样例

6

4

题解：

　　对每个数分解素因子，找其中最小的两个（可以相等）相乘就是结果（这个数可以很大，所以要long long输出。

　　对一个小于等于n的数分解素因数的时间复杂度为sqrt(n)(你用<=sqrt(n)的数去筛，筛完之后最后的一个数要么是1要么是一个质数，这个很好证明），所以暴力解这道题的时间复杂度就为100*sqrt(2*10^9)<10^7，即时间复杂度为o(10^7)，完全够解这道题。

代码1：

　　预处理，先筛出sqrt(n)以内的素数，再用这些素数去分解素因数。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn = 1e5 + ;

 typedef long long LL;

 int n;

 int p[maxn], tot;

 int tot_f;

 int fac[maxn];

 int sift[maxn];

 void prepare() {

     //这个预处理能将时间复杂度降到o(100*sqrt(n)/(ln sqrt(n))）即o(10^6)

     memset(sift, , sizeof(sift));

     for (int i = ; i*i <= maxn; i++) {

         if (sift[i] == ) {

             for (int j = i * ; j <= maxn; j += i) {

                 sift[j] = ;

             }

         }

     }

     tot = ;

     for (int i = ; i<maxn; i++) if (sift[i] == ) {

         p[tot++] = i;

     }

 }

 void init() {

     tot_f = ;

 }

 int main() {

     prepare();

     int tc;

     scanf("%d", &tc);

     while (tc--) {

         init();

         scanf("%d", &n);

         while (n--) {

             int x;

             scanf("%d", &x);

             for (int i = ; i<tot && p[i] < x; i++) {

                 while (x%p[i] == ) {

                     fac[tot_f++] = p[i];

                     x /= p[i];

                 }

             }

             if (x != ) fac[tot_f++] = x;

         }

         if (tot_f>) {

             sort(fac, fac + tot_f);

             printf("%lld\n", (LL)fac[] * fac[]);

         }

         else {

             printf("-1\n");

         }

     }

     return ;

 }

代码2：

　　直接分解因式

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn = 1e5 + ;

 typedef long long LL;

 int n;

 int fac[maxn],tot_f;

 void init() {

     tot_f = ;

 }

 int main() {

     int tc;

     scanf("%d", &tc);

     while (tc--) {

         init();

         scanf("%d", &n);

         while (n--) {

             int x;

             scanf("%d", &x);

             for (int i = ; i*i<=x; i++) {

                 while (x%i == ) {

                     fac[tot_f++] = i;

                     x /= i;

                 }

             }

             if (x != ) fac[tot_f++] = x;

         }

         if (tot_f>) {

             sort(fac, fac + tot_f);

             printf("%lld\n", (LL)fac[] * fac[]);

         }

         else {

             printf("-1\n");

         }

     }

     return ;

 }

巴特西

HDU 5428 The Factor 分解因式

题目链接：

The Factor

题解：

代码1：

代码2：

最新文章

热门文章