acm-刷ACM的小伙伴快進HDU 5428The Factor(*)

刷ACM的小伙伴快進HDU 5428The Factor(*)

鏈接在這
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.

Output

Print T answers in T lines.

Sample Input

2
3
1 2 3
5
6 6 6 6 6

Sample Output

6
4

Source

BestCoder Round #54 (div.2)

 有一個數列，FancyCoder沉迷於研究這個數列的乘積相關問題，但是它們的乘積往往非常大。幸運的是，FancyCoder只需要找到這個巨大乘積的最小的滿足如下規則的因子：這個因子包含大於兩個因子（包括它本身；比如，4有3個因子，因此它是滿足這個要求的一個數）。你需要找到這個數字並輸出它。但是我們知道，對於某些數可能沒有這樣的因子；在這樣的情況下，請輸出-1.

我的代碼如下：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define LL long long
using namespace std;
LL a[111],b[111];
int main()
{
    int T;
    cin>>T;
    int i,n;
    while(T--)
    {
        cin>>n;
        int signum=0;
        for(i=1;i<=n;i++)
        {
            scanf("%ld",&a[i]);
           for(int j=2;j<=sqrt(a[i]);j++)
            {
                if(a[i]%j==0){
                    b[++signum]=j;
                }break;
            }
            if(a[i]!=1&&a[i]%2!=0||a[i]==2){
                b[++signum]=a[i];
            }

        }
        if(signum<2)
            cout<<-1<<endl;
        else{
            sort(b+1,b+signum+1);
            long long desnum=b[1]*b[2];
            cout << desnum <<endl;
        }
    }
    return 0;
}

結果一直顯示Wrong Answer，研究了一天了，求大神解答

最佳回答：

稍微修改了下你的代碼，accepted了

 #include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define LL long long
using namespace std;
LL a[111],b[111111];
int main()
{
    int T;
    cin>>T;
    int i,n;
    while(T--)
    {
        cin>>n;
        int signum=0;
        for(i=1;i<=n;i++)
        {
            scanf("%ld",&a[i]);
            LL tempa=a[i];//保存a[i]被除後的剩余
            int countf=0;//只保留a[i]最小的兩個素因子
           for(int j=2;j<=sqrt(a[i]);j++)
            {
                if(tempa%j==0){//第一個或第二個素因子
                    tempa=tempa/j;//剩余
                    b[++signum]=j;//保存
                    b[++signum]=tempa;//保存和這個因子配對的大於sqrt(a[i])的素因子（例子：26 37，結果應該是26，但是13是不會循環到的）

                    countf++;
                    if(countf==2){//判斷是否是第二個素因子
                        break;
                                        }
                    if(tempa%j==0){//如果上面是第一個素因子，試下剩余是否仍然包含這個素因子，比如 3 8，2是8的第一個，但是剩余4仍然有2
                        b[++signum]=j;
                         b[++signum]=tempa;

                        break;
                    }
                } 
            }
            if(a[i]!=1&&countf==0){//如果不是1而且沒有素因子，就是素數，直接加入
                b[++signum]=a[i];
            }

        }
        if(signum<2)
            cout<<-1<<endl;
        else{
            sort(b+1,b+signum+1);
            long long desnum=b[1]*b[2];
            cout << desnum <<endl;
        }
    }
    return 0;
}