Competitive-Programming/Almost All Divisors.cpp at master · aca123321/Competitive-Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<bits/stdc++.h>
using namespace std;

#define lli long long int
#define pb push_back
#define f first
#define sec second

main()
{
    lli i,n,x,y,sum=0,a,b,c,t,flag;
    cin>>t;
    vector<lli> v;

    while(t--)
    {
        cin>>n;
        v.clear();
        flag = 0;

        for(i=0;i<n;i++)
        {
            cin>>a;
            v.pb(a);
        }

        sum = 1;
        sort(v.begin(),v.end());

        for(i=0;i<n;i++)
        {
            sum = (sum*v[i])/(__gcd(sum,v[i]));
        }

        if(n%2 == 0)
        {
            for(i=0;i<(n/2);i++)
            {
                a = v[i];
                b = v[n-1-i];
                c = a*b;

                if(c != sum)
                {
                    if(c%sum != 0)
                    {
                        cout<<-1<<endl;
                        flag = 1;
                    }
                    else
                    {
                        if(sum<c)
                        {
                            sum = c;
                        }
                    }
                }

                if(flag == 1)
                {
                    break;
                }
            }
        }

        else
        {
            for(i=0;i<(n/2);i++)
            {
                a = v[i];
                b = v[n-1-i];
                c = a*b;

                if(c != sum)
                {
                    if(c%sum != 0)
                    {
                        cout<<-1<<endl;
                        flag = 1;
                    }
                    else
                    {
                        if(sum<c)
                        {
                            sum = c;
                        }
                    }
                }

                if(flag == 1)
                {
                    break;
                }
            }

            if((v[n/2]*v[n/2])%sum != 0 && flag == 0)
            {
                cout<<-1<<endl;
                continue;
            }
            else if((v[n/2]*v[n/2])%sum == 0 && flag == 0)
            {
                sum = (v[n/2]*v[n/2]);
            }
        }

        if(flag == 0)
        {
            for(i=0;i<n;i++)
            {
                if(sum == v[i])
                {
                    sum *= 2;
                }

                if(sum%v[i] != 0)
                {
                    cout<<-1<<endl;
                    flag = 1;
                    break;
                }
            }

            if(flag == 0)
            {
                cout<<sum<<endl;
            }
        }
    }


}