# Count number of pairs $(a,b)$ in an array such that $(a + b)$ divides $(a * b)$

We are given an array of size $N$ with integer entries $> 0$. We have to count the number of all such pairs $(a,b)$ with $a \leq b$ such that $a*b$ is divisible by $a + b$.

The obvious naive way is to check every pair and it takes $\mathcal{O}(N^2)$ time. This seems to be more of a maths problem rather than algorithmic.

Is it possible to improve the time complexity of this problem?

I have this idea.

Let $d = gcd(a,b)$. For some $x,y \in \mathbb{N}$ we have $a = dx$ and $b = dy$ with $gcd(x,y) = 1$. Since $gcd(x,x + y) = 1$ and $gcd(y,x + y) = 1$, we have

$(a+b) \lvert ab \Rightarrow d(x+y) \lvert d^2xy \Rightarrow (x+y) \lvert dxy \Rightarrow (x+y) \lvert d$

Let $d = k(x + y)$ for some $k \in \mathbb{N}$. Then $a = kx(x+y)$ and $b=ky(x+y)$ and the problem reduces to finding all such triplets $(k,x,y)$ with $x < y$ and $gcd(x,y) = 1$.

• What is the domain of $a$ and $b$? All real integers? – ubadub Sep 17 '18 at 18:32
• We can assume the array has only integers $> 0$. – chelsea Sep 17 '18 at 20:36
• Please edit the question to incorporate that information into the question. – D.W. Sep 18 '18 at 1:18
• I've made an edit. – chelsea Sep 18 '18 at 6:25
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Sep 18 '18 at 9:26