codeforces1165D. Almost All Divisors

题目链接 琪亚娜世界第一可爱

给出n个因数，求最小的数num，使得除1和num以外的因数都在给出的这n个数中，如果不存在输出-1 。

很水的一道题，但比赛的时候总在想怎么用lcm做，然后因为不知怎么预处理-1的情况，就一直卡。
但实际上，对给出的n个数排序，从两端各取一个数，如果存在的话，这两个数的乘积一定是相同的。
然后再判断是否所有的因数都在这n个数中，最后输出答案

复杂度的话，主要在最后一个判断里，就是判断是否所有因数都在这n个数中，最多可能执行1e6次，因为超过1e6的值不会出现在这n个数里，所以出现超过1e6的因数就会判错，最多共有25组。

#pragma GCC diagnostic error "-std=c++11"
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define Pair pair<int,int>
#define re return

#define getLen(name,index) name[index].size()
#define mem(a,b) memset(a,b,sizeof(a))
#define Make(a,b) make_pair(a,b)
#define Push(num) push_back(num)
#define rep(index,star,finish) for(register int index=star;index<finish;index++)
#define drep(index,finish,star) for(register int index=finish;index>=star;index--)
using namespace std;
const int maxn=305;

int N;
ll factor[maxn];
map<ll,bool> appear;
int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        //ini
        appear.clear();

        scanf("%d",&N);
        rep(i,0,N){
            scanf("%lld",&factor[i]);
            appear[factor[i]]=true;
        }
        sort(factor,factor+N);

        int finish=N/2+N%2;
        ll lcm=factor[0]*factor[N-1];
        bool safe=true;
        rep(i,1,finish){
            if(lcm!=factor[i]*factor[N-i-1]){
                safe=false;
                break;
            }
        }
        if(!safe){
            printf("-1\n");
            continue;
        }

        for(register ll i=2;i*i<=lcm;i++){
            if(lcm%i)
                continue;
            if(!appear[i] || !appear[lcm/i]){
                safe=false;
                break;
            }
        }
        if(safe){
            printf("%lld\n",lcm);
        }else{
            printf("-1\n");
        }
    }

    re 0;
}