We have a list. divide the list element into two groups such that when the product of the numbers of two groups is taken and their GCD is calculated, it came out to be 1. Answer the number of ways in which the list element can be divided into two groups following the property.
Note: The value of a group is the product of the numbers in that group. The output can be very large, so you need to take the modulo 10^9 + 7 of the answer and print it.
sample Input :
2 3 2 3 5 4 2 4 6 8
Constraints
1<= T <=5
1<= N <=10^5
1<= list_element <=10^6
Input Format
The first line consists of the number of test cases, T.
The first line of each test case consists of the number of element, N.
The second line of each test case consists of the N space-separated integers of the list.
My code is working fine but it is consuming too much time. Please help.
Below is my code.
public static List<long> GroupList = new List<long>();
static long G_Counter = 0;
static void Main(string[] args)
{
int TestCases = int.Parse(Console.ReadLine());
List<List<long>> groupMember = new List<List<long>>();
for (int i = 0; i < TestCases; i++)
{
string People = Console.ReadLine();
groupMember.Add(Console.ReadLine().TrimEnd().Split(' ').ToList().Select(arrTemp => Convert.ToInt64(arrTemp)).ToList());
}
CreateGroup(groupMember);
}
static void CreateGroup(List<List<long>> Group)
{
int count=Group.Count();
List<long> GroupCount = new List<long>();
for (int k = 0; k < count; k++)
{
int lenght = Group[k].Count();
G_Counter = 0;
heapPermutation(Group[k].ToArray(), lenght, lenght);
GroupList.Add(G_Counter);
}
int GC = GroupList.Count();
for (int i = 0; i < GC; i++)
{
Console.WriteLine(GroupList[i]);
}
Console.ReadLine();
}
static bool printArr(long[] a, int n)
{
var k = 2;
bool val = false;
var res = Enumerable.Range(0, (a.ToList().Count - 1) / k + 1)
.Select(i => a.ToList().GetRange(i * k, Math.Min(k, a.ToList().Count - i * k)))
.ToList();
for (int i = 0; i != res.Count(); i++)
{
var result1 = res[i].Aggregate((c, b) => b * c);
for (int j = i + 1; j != res.Count(); j++)
{
var result2 = res[j].Aggregate((c, b) => b * c);
long gcd_val= gcd(result1, result2);
if (gcd_val == 1)
{
val = true;
break;
}
else {
break;
}
}
}
return val;
}
static void heapPermutation(long[] a, int size, int n)
{
// if size becomes 1 then prints the obtained
// permutation
if (size == 1)
{
var result= printArr(a, n);
if (result == true)
{
G_Counter++;
}
}
for (int i = 0; i < size; i++)
{
heapPermutation(a, size - 1, n);
// if size is odd, swap first and last
// element
if (size % 2 == 1)
{
long temp = a[0];
a[0] = a[size - 1];
a[size - 1] = temp;
}
// If size is even, swap ith and last
// element
else
{
long temp = a[i];
a[i] = a[size - 1];
a[size - 1] = temp;
}
}
}
static long gcd(long a, long b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}