Chhota Bheem and GCD
All submissions for this problem are available.
We all know that our friend Bheem likes gcd of numbers very much. One day Kaalia challenged him with a new problem with gcd. He gave Bheem N numbers and asked to divide the given set of numbers into some disjoint subsequences. Two numbers a and b belong to same subsequence if gcd(a,b)>1. Value of each subsequence is the largest number in that subsequence. He challenged Bheem to find the product of values of all subsequences.
Help Bheem win this challenge.
Note: if gcd(a,b) >1, gcd (b,c) >1 then a,b,c will be in same subsequence even if gcd(a,c) = 1.
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N denoting the number of elements in the set.
- The second line contains N space-separated integers A1, A2, ..., AN elements in the set.
- For each test case output a single number, the answer to given problem modulo 1000000007, in a separate line.
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 200
- 1 ≤ Ai ≤ 109
Input: 2 4 2 4 3 9 3 2 3 6 Output: 36 6
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.