本文主要是介绍hdu 5428 The Factor(数论),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:http://acm.hdu.edu.cn/showproblem.php?pid=5428
The Factor
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1707 Accepted Submission(s): 527
Problem Description
There is a sequence of n positive integers. Fancycoder is addicted to learn their product, but this product may be extremely huge! However, it is lucky that FancyCoder only needs to find out one factor of this huge product: the smallest factor that contains more than 2 factors(including itself; i.e. 4 has 3 factors so that it is a qualified factor). You need to find it out and print it. As we know, there may be none of such factors; in this occasion, please print -1 instead.
Input
The first line contains one integer T (1≤T≤15) , which represents the number of testcases.
For each testcase, there are two lines:
1. The first line contains one integer denoting the value of n (1≤n≤100) .
2. The second line contains n integers a1,…,an (1≤a1,…,an≤2×109) , which denote these n positive integers.
For each testcase, there are two lines:
1. The first line contains one integer denoting the value of n (1≤n≤100) .
2. The second line contains n integers a1,…,an (1≤a1,…,an≤2×109) , which denote these n positive integers.
Output
Print T answers in T lines.
Sample Input
2 3 1 2 3 5 6 6 6 6 6
Sample Output
6 4
分析:最近刚学java,所以来做道题,图论,数据结构啥的代码量太大,所以挑数论来做。这题的大意是,求出若干个数字的乘积的最小因子(不小于4)。
弄清问题的本质,写代码就轻松不少。。
弄清问题的本质,写代码就轻松不少。。
import java.util.*;
public class Main {static final int maxn=(int)(2e5);static long[] fac=new long [maxn],sum=new long [maxn]; //数组长度只能用int?public static int cnt;static void resolve(long x){for(long i=2;i*i<=x;i++){while(x%i==0){x/=i;fac[cnt++]=i;}}if(x>1){fac[cnt++]=x;}}public static void main(String[] args) {long t,n,a;Scanner sc=new Scanner(System.in);t=sc.nextLong();for(int k=0;k<t;k++){n=sc.nextLong();cnt=0;for(int i=0;i<n;i++){a=sc.nextLong();resolve(a);}Arrays.sort(fac,0,cnt); //和C++的sort类似if(cnt<2)System.out.println(-1);else System.out.println(fac[0]*fac[1]);}}}
这篇关于hdu 5428 The Factor(数论)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!