I was given this question by a friend:
"You are given 3 sets of size n, X,Y and Z. Devise an algorithm to find maximum number of different pairings (u,v,w,x) such that u,v,w,x belong to X,Y,Z and X respectively (u is not equal to x) and gcd(u,v,w,x)>1."
My approach is to create new sets S and T, such that S contains pair (u,v) (create a node A) with gcd(u,v)>1 and T contains (w,x) with gcd(w,x)>1 (node B). If gcd(u,v,w,x)>1 add an edge between A and B. Now find maximum matching in this bipartite graph.
But he isn't satisfied and says I didn't use the gcd property and the problem can be reduced significantly. Can this algorithm be improved?