MrTEK's blog

By MrTEK, history, 10 days ago, In English,

Determine x,y and d for the integers a and b such that: a*x+b*y=d where d is the greatest common divisor of a and b(0<=a,b<=2.10^9)

INPUT: 2 integers a and b OUTPUT: 3 integers x,y and d. if there are more than one solution you can print any of them.

 
 
 
 

»
10 days ago, # |
  Vote: I like it -17 Vote: I do not like it

You know a and b, calculate d using __gcd(a,b). Apply a binary search for x, such that y lies in permissible limits.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I think there is no need for binary search. its simply extended Euclid algorithm.

    E : ax + by = d . Where a, b, x, y, and d are Integers (which mean finding the integer solutions for this equation since i guess there are unlimited solutions in R²) have a solution if and only if d decides the greater common divisor of a and b.

    you can find more details about gcd and extended euclid algos and useful things in this link : Here (Hackerearth practice Math : Number Theory 1

    Correct me if any thing is wrong, thank you .

»
10 days ago, # |
  Vote: I like it +3 Vote: I do not like it