# Doubt regarding Maximum Bipartite Matching

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?

• This problem is from ongoing programming contest. – preetsaimutneja Jul 9 '14 at 17:56
• What have you tried, to improve your algorithm? What are your thoughts? Are you familiar with the property that that $gcd(a,b,c) = \gcd(a,\gcd(b,c)) = \gcd(\gcd(a,b),c)$? – D.W. Jul 9 '14 at 22:11
• what contest is it from? ref? – vzn Jul 10 '14 at 2:29
• codechef.com/JULY14/problems/GNUM – preetsaimutneja Jul 10 '14 at 3:40

$$\gcd(u,v,w,x) = \gcd(\gcd(u,v),\gcd(w,x)).$$
A maximal matching doesn't seem like the right approach. The maximal matching algorithm you list will never choose two 4-tuples $(u,v,w,x),(u',v',w',x')$ such that $(u,v)=(u',v')$. Thus, it won't produce the correct answer to the problem: it won't output the maximum number of different 4-tuples.