Блог пользователя Saucemaster102

GCD of Cartesian product of two arrays
Автор Saucemaster102, история, 2 года назад, По-английски

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

Теги gcd
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How do you take the gcd of two pairs?

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)
→ Ответить