2 void cpp1 void_cpp1 于 2016.02.28 21:12 提问

刷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,研究了一天了,求大神解答

6个回答

u013596119
u013596119   Rxr 2016.02.29 10:48
已采纳

稍微修改了下你的代码,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;
}
void_cpp1
void_cpp1 回复DarthHaric: 明白了,谢谢
接近 2 年之前 回复
u013596119
u013596119 回复void_cpp1: 根据你下面发的AC的代码,300是否合适?因为每一个数字最多会保存两个素因子还有它本身到b中,最多100个数字,所以300个?我的算法里要400吧
接近 2 年之前 回复
void_cpp1
void_cpp1 另外就本题而言定义b[236]会RE,而b[237]时会AC,想请教一下数组b的大小定多少合适呢?
接近 2 年之前 回复
devmiao
devmiao   Ds   Rxr 2016.02.28 22:46
void_cpp1
void_cpp1 谢谢!我先看看
接近 2 年之前 回复
Mr_dsw
Mr_dsw   Ds   Rxr 2016.02.28 23:05

倪可以去对应的讨论区问问,那边应该有

u013596119
u013596119   Rxr 2016.02.29 10:10

试下3 8,你的结果是6,应该是4

void_cpp1
void_cpp1 谢谢,我把题意理解错了
接近 2 年之前 回复
void_cpp1
void_cpp1   2016.02.29 12:34

AC了,哈哈谢谢

void_cpp1
void_cpp1   2016.02.29 18:39

受DarthHaric的提醒自己改了一下,终于AC了

 #include <iostream>
#include <cstdio>
#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]);
            int num=2;   //用num来控制求得的每个数的质因数不超过2个
           for(int j=2;j*j<=a[i]&&num;j++)
            {
                if(a[i]%j==0){
                    b[++signum]=j;
                    a[i]/=j;
                    j=1;
                    num--;
                    }
            }
            if(a[i]!=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;
}


Csdn user default icon
上传中...
上传图片
插入图片