# GCD Groups with list

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();
}
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);
}
int GC = GroupList.Count();
for (int i = 0; i < GC; i++)
{
Console.WriteLine(GroupList[i]);
}
}
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);
}

• Is this from a programming challenge/contest? Can you provide a link to the problem description? That might help to understand the task. – Some examples would also be helpful. – Martin R Oct 25 at 11:37
• Is this understanding correct? Given $N$ numbers $a_1, \ldots, a_N$ we have to determine the number of ways to split these numbers into two groups $b_1, \ldots, b_k$ and $c_1, \ldots, c_l$ such that $\gcd(b_1 \cdots b_k, c_1 \cdots c_l) = 1$. – Martin R Oct 25 at 11:45
• e.g. there are 3 numbers as {2,3,5} 1. Group 1: {2, 3}; Product = 6 Group 2: {5} gcd(6, 5) = 1 The problem is to find the number of ways of dividing the dummies into groups such that the gcd of their product is 1. For the given set of dummies, there are 6 ways of dividing them into two groups following the property. – DC_Sharp Oct 25 at 11:53
• @DC_Sharp: Please add all relevant information to the question itself, not to the comments. – Known restrictions (how large can $N$ and the numbers $a_i$ be) would also be good to know. – Martin R Oct 25 at 11:53
• Well, this is a task where the “brute force attack” simply does not work. For $N = 10^5$ there are $2^N \approx 10^{30103}$ partitions, that is far more than the number of atoms in the universe. – You'll need some math to understand and simplify the problem. This might give you some inspiration. – Martin R Oct 25 at 12:23