### MrTEK's blog

By MrTEK, history, 6 months ago, ,

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.

 » 6 months ago, # |   -17 You know a and b, calculate d using __gcd(a,b). Apply a binary search for x, such that y lies in permissible limits.
•  » » 6 months ago, # ^ |   +3 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 1Correct me if any thing is wrong, thank you .
•  » » » 6 months ago, # ^ |   +4 Thanks
 » 6 months ago, # |   +3
•  » » 6 months ago, # ^ |   +3 Thanks