Saucemaster102's blog

GCD of Cartesian product of two arrays
By Saucemaster102, history, 2 years ago, In English

hey guys , a while back I had come across this problem(sorry I don’t have the link to problem statement) , it was basically, given two arrays a and b of size n and m , find the gcd of all the elements of the resultant array c where c is the Cartesian product of a and b , I could not figure out a better approach than O(n*m) Does anyone have a better approach ?

Constraints : n,m<1e+5

Tags gcd
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How do you take the gcd of two pairs?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

First, let's take a look at the case where the size of array a is 1. We'll have the following answer:

answer = GCD( a[0] * b[i], a[0] * b[i+1], ...)

This can be simplified to answer = a[0] * GCD(b[i], b[i+1]...) = a[0] * GCD(b).

Now, what if we have a bigger array a, then we have the following derivation:

answer = GCD( a[0] * GCD(b), a[1] * GCD(b), ...)
       = GCD( a[0], a[1], ...) * GCD(b) =
       = GCD(a) * GCD(b)
→ Reply