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$.

  • $\begingroup$ What is the domain of $a$ and $b$? All real integers? $\endgroup$ – ubadub Sep 17 '18 at 18:32
  • $\begingroup$ We can assume the array has only integers $> 0$. $\endgroup$ – chelsea Sep 17 '18 at 20:36
  • $\begingroup$ Please edit the question to incorporate that information into the question. $\endgroup$ – D.W. Sep 18 '18 at 1:18
  • $\begingroup$ I've made an edit. $\endgroup$ – chelsea Sep 18 '18 at 6:25
  • $\begingroup$ 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! $\endgroup$ – Raphael Sep 18 '18 at 9:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.