Almost All Divisors（求因子个数及思维）

发布时间：2020-12-14 01:10:30 所属栏目：Linux 来源：网络整理

导读：---恢复内容开始--- We guessed some integer number? x x. You are given a list of? almost all?its divisors.? Almost all?means that there are? all divisors except? 1 1and? x x?in the list. Your task is to find the minimum possible integer? x

---恢复内容开始---

We guessed some integer number?

Your task is to find the minimum possible integer?

You have to answer?

Input

The first line of the input contains one integer?

The first line of the query contains one integer?

The second line of the query contains?

Output

For each query print the answer to it.

If the input data in the query is contradictory and it is impossible to find such number?

Example

input

Copy

2
8
8 2 12 6 4 24 16 3
1
2

output

Copy

48
4

思路：求出因子个数，看是否这n个数是否包含这n个因子数，然后判断一下再判断一下这n个数是否是他的因子

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<map>
#include<cmath>
const int maxn=1e5+5;
typedef long long ll;
using namespace std;
ll count(ll n){
    ll s=1;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0){
            int a=0;
            while(n%i==0){
                n/=i;
                a++;
            }
            s=s*(a+1);
        }
    }
    if(n>1) s=s*2;
    return s;
}
ll a[maxn];
int main()
{
   int T;
   cin>>T;
   int n;
   while(T--)
   {
       scanf("%d",&n);
       ll maxx=2;
       ll minn=10000000;
       ll x;
       for(int t=0;t<n;t++)
       {
           scanf("%lld",&a[t]);
           maxx=max(a[t],maxx);
           minn=min(a[t],minn);
    }
    ll ans=maxx*minn;
    bool flag=false;
    for(int t=0;t<n;t++)
    {
        if(ans%a[t]!=0)
        {
            flag=true;
        }
    }
    if(count(ans)-2==n&&flag==false)
    printf("%lldn",ans);
    else
    {
        printf("-1n");
    }
    

   }
   return 0;
}

---恢复内容结束---

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!