FTNUM - Editorial

Author: Harsh Dwivedi
Tester: Abhinav Prakash

SIMPLE

PREREQUISITES:

Data-Structures, Math.

PROBLEM:

We are given the divisors of a number x ( divisors except 1 and x itself ) , you have to print the number if only it is possible.

QUICK EXPLANATION:

Divisors of 6 are ( 1,2,3,6) Therefore, Divisors except 1 and the number 6 itself are ( 2 , 3). Thus, ans = 6.

SOLUTIONS:

Setter's Solution

import java.io.IOException;
import java.util.*;

public class Main {
private static FastScanner sc = new FastScanner();

public static void main(String[] args) {
int t = 0;
if (sc.hasNext())
t = sc.nextInt();
for (int i = 1; i <= t; i++) {
solve();
}
}

public static void solve() {
int n = sc.nextInt();
Arrays.sort(a);
long ans = a[0] * a[n - 1];
long[] b = new long[100001];
Vector<Long> x = new Vector<>();
for (int i = 0; i < n; i++)
Collections.sort(x);
Vector<Long> y = new Vector<>();
for (int i = 2; (long) i * i <= ans; i++) {
if (ans % i == 0) {
if ((long) (i * i) != ans) {
}
}
}
Collections.sort(y);
for (int i = 0; i < n; i++) {
if (!x.get(i).equals(y.get(i))) {
System.out.println(-1);
return;
}
}
System.out.println(ans);
}

private static long gcd(long a, long b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}

static void sort(int[] a) {
ArrayList<Integer> l = new ArrayList<>();
for (int i : a) l.add(i);
Collections.sort(l);
for (int i = 0; i < a.length; i++) a[i] = l.get(i);
}

static class FastScanner {
StringTokenizer st = new StringTokenizer("");

boolean hasNext() {
if (st != null && st.hasMoreTokens()) {
return true;
}
String tmp;
try {
br.mark(1000);
if (tmp == null) {
return false;
}
br.reset();
} catch (IOException e) {
return false;
}
return true;
}

String next() {
while (!st.hasMoreTokens())
try {
} catch (IOException e) {
e.printStackTrace();
}
return st.nextToken();
}

int nextInt() {
return Integer.parseInt(next());
}

int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = nextInt();
return a;
}

long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = nextLong();
return a;
}

long nextLong() {

return Long.parseLong(next());
}

double nextDouble() {
return Double.parseDouble(next());
}
}
}
Tester's Solution

#include<bits/stdc++.h>

using namespace std;

int __gcd(int a, int b)
{
if( b == 0 ) return a ;
a %=b ;
return __gcd(b, a) ;
}

vector<long long> get_divisors(long long num)
{
set<long long> val ;
for(long long i = 2; i*i <= num; i++)
if( !(num%i) )
{
val.insert(i) ;
val.insert(num/i) ;
}

vector<long long> ans(val.begin(), val.end()) ;
return ans ;
}

int main( int argc, char **argv )
{
int t, n ;
cin >> t ;
while( t-- )
{
cin >> n ;
vector<long long> divs(n, 0) ;

for(int i = 0; i < n; i++)
cin >> divs[i] ;

set<long long> divset(divs.begin(), divs.end()) ;
sort( divs.begin(), divs.end() ) ;

long long num = divs[n-1] * divs[0] ;

vector<long long> vals = get_divisors(num) ;
bool done = true ;
for(int i = 0; i < vals.size(); i++)
if( !divset.count(vals[i]) )
{
done = false ;
break ;
}

if( done ) cout << num << endl ;
else cout << -1 << endl ;

}

return 0;
}