SP18165 NCOPRIME - Coprime Pairs

Mr. Yagami is playing a game of arrays. He is given two random arrays **A** and **B** consisting of **N** positive integer elements. Game starts by Mr. Yagami assigning **0 or 1** to each element in **A and B**. After this assignment is done, a graph is constructed with a node for each element in the array A and B (**2N** nodes) and no edges. The game proceeds with a valid move being defined in the following way: - One of the arrays from **A** or **B** is selected. From the selected array, an element which has been marked 0 is chosen. Let us call this element as **X**. - A set of elements, **Y**, are chosen from the array, which was not chosen in the first step, such that all elements of **Y** should be marked as **1** and all elements of **Y** should be greater than **X** and no element of **Y** should be coprime to **X**. - Finally an edge is drawn from the node labelled **X** to all the nodes corresponding to the elements in set **Y**. There can only be a single edge between any **2** nodes in the graph. He can make as many valid moves. Mr. Yagami receives **1** point for each edge that is drawn in the graph. Mr. Yagami is very clever, so he makes the initial assignment in such a way that it maximizes the number of points he receives in the game. You have to return the maximum number of points that Mr. Yagami can receive.

N/A

N/A