It can be solved using a Maximum Spanning Tree Approach (it works for the given test cases , atleast)

In this problem, each operation after placing the first element contributes a score equal to the gcd of the newly inserted element and some previously inserted element. With an optimal ordering, this is equivalent to choosing a spanning tree on a complete graph (with nodes representing the array elements and edge weights equal to the gcd of their values) so that the sum of the edge weights is maximized.

i can think this ~~~~~ //this is code

include <bits/stdc++.h>

using namespace std;

int main(){ int n; cin>>n; vectorv(n); for(int i=0;i<n;i++){ cin>>v[i]; } sort(v.rbegin(),v.rend()); map<int,int>mp; for(int j=1;j*j<=v[0];j++){ if(v[0]%j==0){ int div1=j; int div2=v[0]/j; mp[div1]=1; mp[div2]=1; } } int ans=0; for(int i=1;i<n;i++){ int val=v[i]; int maxi=1; for(int j=1;j*j<=val;j++){ if(val%j==0){ int div1=j; int div2=val/j; if(mp.find(div1)!=mp.end()){ maxi=max(maxi,div1); } if(mp.find(div2)!=mp.end()){ maxi=max(maxi,div2); } } } ans=ans+maxi; for(int j=1;j*j<=val;j++){ if(val%j==0){ int div1=j; int div2=val/j; mp[div1]=1; mp[div2]=1; } } } cout<<ans<<endl; } ~~~~~

Let make a graph.

Vertex = X[i] Vertex X[i] and X[j] have a edge if gcd(X[i], X[j]) > 1 How many edges we can have?

So, each X have O(sqrt(X)) divisors. it mean that X can be connected with no more than O(sqrt(X)) vertex -> no more than O(Nsqrt(X)) edges.

let find max spanning tree for each connectivity components and our ans is (number of connectivity components — 1) + (Sum of spanning tree weights)

how much time was given for this problem to solve in the coding round?

I think you can do this greedily. What you do first is iterate through d = 1e4 to 1 (I am trying to find out the largest possible gcd with the help of d), then:
1. Initially when all elements are in left(called x in the question) and right(called y in the question) is empty, you can just try to find out if d divides any two (or more) elements in left. If yes, put them the largest in the right.
2. When there are elements on the right, find out if d divides atleast one element in the left and atleast one element in right. If yes, bring these elements in the left to right.
3. Keep repeating till you get d= 1.

As to why this is optimal, suppose instead of putting an element to the right with d'', you put it to the right later at d' (d'' > d'). Then, d'' was viable because there was an element which was also divisible by d'' in the right, and upon discovering d', this won't go away (because you are only adding elements to the right). Therefore, d'' will always be an option, even when dividing by d' and it would make sense to choose d' when d'' is an option.
If there is any error in my approach or some confusion, please tell me (along with my mistake in my proof I am not really good at proofs)!

for numbers <= 1e4 there can be atmost (25-50) divisors (lets take it 100)

now sort array in reverse order

now iterate from largest element to smallest

for current element iterate over its divisors (from largest to smallest) and check if any of its multiple has been added to y (easily maintainable using a hashmap)

add it to ans move the current element to array y and increase count for its divisors.

O(100*n*logn) over all test cases

isn't this greedy correct?