Extended Euclid Coefficients
Hard
Computer Mathematics
GCD/LCM & Euclid
34 views
Problem Statement
Find x,y such that ax+by=gcd(a,b). Print gcd x y.
Input Format
Two integers a b.
Output Format
g x y.
Example
30 18
6 -1 2
Constraints
|a|,|b|
Input / Output Format
Input Format
Two integers a b.
Output Format
g x y.
Constraints
|a|,|b|
Examples
Input:
30 18
Output:
6 -1 2
Example Solution (Public)
Use recursive extended Euclid: if b==0 return (a,1,0). Else compute for (b,a%b) then back-substitute.
Official Solution Code
Use recursive extended Euclid: if b==0 return (a,1,0). Else compute for (b,a%b) then back-substitute.
Please login to submit solutions.