import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Solution {
static Scanner sc = new Scanner(System.in);
public static void main(String args[]) {
int te = sc.nextInt();
for (int i = 0; i < te; i++) {
BigInteger n = sc.nextBigInteger();
int l = sc.nextInt();
BigInteger[] products = new BigInteger[l];
for (int j = 0; j < l; j++) {
products[j] = sc.nextBigInteger();
}
BigInteger[] primes = new BigInteger[l + 1];
int k = 0;
for (int j = 0; j < l; j++) {
Map.Entry<BigInteger, BigInteger> temp = primeFactors
(products[j]);
if (j == 0) {
// initially both the prime factors should be inserted
Map.Entry<BigInteger, BigInteger> temp1 = primeFactors
(products[j + 1]);
if (temp.getKey().equals(temp1.getKey()) || temp.getKey
().equals(temp1.getValue())) {
primes[k] = temp.getValue();
primes[++k] = temp.getKey();
} else {
primes[k] = temp.getKey();
primes[++k] = temp.getValue();
}
} else if (temp.getKey().equals(primes[k - 1])) {
// one the prime divides with previous product value so we need to skip it
primes[k] = temp.getValue();
} else {
primes[k] = temp.getKey();
}
k++;
}
for (int j = 0; j < primes.length; j++) {
System.out.println(primes[j]);
}
Set<BigInteger> set = new HashSet<>();
Collections.addAll(set, primes);
// removes duplicates from primes
List<BigInteger> alpha = new ArrayList(set);
Collections.sort(alpha); // sorts the List
String s = "";
for (int j = 0; j < primes.length; j++) {
s += (char) ('A' + alpha.indexOf(primes[j]));
// append charecters to string s
}
System.out.print("Case #" + Integer.toString(i + 1) + ": " + s);
System.out.println();
}
}
/* Generate Prime Factors returns a key, value pair which are factors of
BigInteger */
public static Map.Entry<BigInteger, BigInteger> primeFactors(BigInteger
n) {
BigInteger x = BigInteger.valueOf(2);
Map.Entry<BigInteger, BigInteger> temp = new AbstractMap.SimpleEntry
(x, x);
if (n.mod(x).equals(BigInteger.valueOf(0))) {
temp = new AbstractMap.SimpleEntry(BigInteger.valueOf(2), n.
divide(BigInteger.valueOf(2)));
return temp;
}
for (BigInteger i = BigInteger.valueOf(3); i.multiply(i).compareTo
(n) <= 0; i = i.add(x)) {
if (n.mod(i).equals(BigInteger.valueOf(0))) {
temp = new AbstractMap.SimpleEntry(i, n.divide(i));
return temp;
}
}
return temp;
}
}
This i have written the code in java using BigInteger. Though i executes
correctly for various inputs and outputs, it results in WA. Could any one
please check this once?
On Tuesday, March 31, 2020 at 11:29:54 PM UTC+5:30, porker2008 wrote:
>
> C++ does not have built-in support for big integers
>
> You can consider using other languages like python or Java(BigInteger)
>
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/4d1ba38c-cb72-4220-af55-b3fa176cece7%40googlegroups.com.
