LushoPlusPlus's blog

GCD
By LushoPlusPlus, history, 4 years ago, In English

Hi dear community!

last day I was solving a GCD problems, it was easy for a,b <= 10^5 but when the limits change to a,b <=10^9, I got TLE how can I optimize this? what that it mean GDC(a,b)=GCD(b,a%b)? and how can I apply this to solve the problem?.

thanks in advanced

  • Vote: I like it
  • -19
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Consider the GCD of 10 and 45. Whatever it is, it divides 10. So if we know the GCD of 10 and 5, then we know that is also the GCD of 10 and 45. After all, if it divides 10, it also divides 40, so we can easily add 40 to 5 to get 45, without removing relevant factors.

If you use this algorithm, you can find the GCD of two numbers in log(n) time. A good demonstration of that can be seen here: https://m.youtube.com/watch?v=JUzYl1TYMcU

(that was the first YouTube video result after searching GCD)

→ Reply