题目链接:

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)a​1​​,…,a​n​​ (1≤a​1​​,…,a​n​​≤2×10​9​​), 表示这个数列。
输出描述
输出TT行TT个数表示每次询问的答案。
输入样例
2
3
1 2 3
5
6 6 6 6 6
输出样例
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 ;
}
05-08 08:14
查看更多