0
$\begingroup$

In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), highest common factor (hcf), or greatest common measure (gcm), of two or more integers (at least one of which is not zero), is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4.

Given an integer N. Now Find how many GCD(A,B)=B Where 1≤A≤B≤N For example,for N=3 the result will be 5.It can be found in the following way.

GCD(1,1)=1 OK

GCD(1,2)=1

GCD(1,3)=1

GCD(2,1)=1 OK

GCD(2,2)=2 OK

GCD(2,3)=2

GCD(3,1)=1 OK

GCD(3,2)=1

GCD(3,3)=3 OK

Here we get 5 combination where GCD(A,B)=B But how can I calculate it for 1≤N≤10^9 efficiently?

$\endgroup$

migrated from programmers.stackexchange.com Oct 5 '14 at 18:58

This question came from our site for professionals, academics, and students working within the systems development life cycle.

  • $\begingroup$ "combination where GCD(A,B)=B" should that say GCD(A,B)=1? $\endgroup$ – Ben Aaronson Oct 5 '14 at 18:15
  • 1
    $\begingroup$ gdc(a,b)==b iff b*n=a for n in N and b<=a $\endgroup$ – ratchet freak Oct 5 '14 at 18:21
  • $\begingroup$ Are you sure you want $A \leq B$ rather than $B \leq A$? $\endgroup$ – Yuval Filmus Oct 6 '14 at 0:16
4
$\begingroup$

Hint: $\mathrm{gcd}(a,b) = b$ iff $b|a$. Since you're only looking for pairs in which $a \leq b$, this forces $a = b$.

$\endgroup$
1
$\begingroup$

You could try using Stein's method, which is especially efficient on binary computers:

$$\gcd(0,v) = v$$ $$\gcd(2u,2v) = 2 \gcd(u,v)$$ $$\gcd(2u+1,2v) = \gcd(2u+1,v)$$ $$\gcd(2u,2v+1) = \gcd(u,2v+1)$$ $$\gcd(2u+1,2v+1) = \gcd(u-v,2v+1)$$

That is:

$$\hbox{gcdcheck}(0,v) = \hbox{true}$$ $$\hbox{gcdcheck}(2u,2v) = \hbox{false}$$ $$\hbox{gcdcheck}(2u+1,2v) = \hbox{false}$$ $$\hbox{gcdcheck}(2u,2v+1) = \hbox{gcdcheck}(u,2v+1)$$ $$\hbox{gcdcheck}(2u+1,2v+1) = \hbox{gcdcheck}(u-v,2v+1)$$

Now implement this using dynamic programming. Use the fact that only the (odd,odd) cases need to be stored.

$\endgroup$
  • $\begingroup$ Do you have ternary computers? $\endgroup$ – The Mean Square Oct 6 '14 at 3:24
  • $\begingroup$ I have large-number APIs for which accessing the binary representation isn't convenient and/or efficient. $\endgroup$ – Pseudonym Oct 6 '14 at 4:01
1
$\begingroup$

Looking at your worked out example, I believe that where you said 1≤A≤B≤N you meant 1≤B≤A≤N. And then your gcd equation only happens if B divides A.

If that is true, then your equation is equivalent to the following. How many pairs (B, A) are there with both less than or equal to N such that A = B * C for some C?

And now we can break into three cases. The cases are:

  1. B < C
  2. B = C
  3. C < B

The number in case 2 is the floor of sqrt(N).

The number in cases 1 and 3 are the same.

The only hard part that is left is counting the number in case 1. And for that we can just run through the possible values of B up to sqrt(N), for each one adding floor(N/B) - B.

In the case of N = 3 the calculation then becomes floor(sqrt(3)) + 2 * ( floor(3/1) - 1) ) = 1 + 2 * (3 - 1) = 5.

This is not very informative, so let's do the case of N = 10. Then the calculation becomes

floor(sqrt(10)) + 2 * ((floor(10/1) - 1) + (floor(10/2) - 2) + (floor(10/3) - 3))
  = 3 + 2 * ((10 - 1) + (5 - 2) + (3 - 3))
  = 3 + 2 * (9 + 3 + 0)
  = 27

This equation requires O(sqrt(N)) terms. So for N around a billion you'll need to do tens of thousands of operations, which is not hard on current computers.

$\endgroup$

Your Answer

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