뭐좀 물을게요

[잘하고싶다(175.204)]

요로케 했는데 저 아래 s,t 가 (a*s)+(b*t)=d 에서 s,t 인데 저걸 구하려면 도대체 어떻게 해야하는거에여

[잘하고싶다(175.204)]

ㄴ유클리드를 이용해서 최대공약수는 구했는데 더 나아가서 s와 t를 구하고 싶다 이말이에요

[ㄹ(123.213)]

s, t 구하는 알고리즘을 작성해야 될껀데요..

[ㄹ(123.213)]

http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

[ㄹ(123.213)]

http://stackoverflow.com/questions/4917003/whats-algorithm-used-to-solve-linear-diophantine-equation-ax-by-c

[잘하고싶다(175.204)]

ㄴ 알고리즘을 작성해야하는건 알고있져 저상태에서 하면 0하고 공약수 상태에서 s,t가 구해지지않나여?

[ㄹ(123.213)]

예를 들어서 보여드릴께요. gcd(42, 30) ... 42 = 30 * 1 + 12, 30 = 12 * 2 + 6, 12 = 6 * 2, 첫 번째 식을 약간 변형해서 두 번째 식에 대입하면 30 = (42 - 30 * 1) * 2 + 6 ∴ -2 * 42 + 3 * 30 = 6

[ㄹ(123.213)]

gcd 구하는 과정에서 나온 결과물을 가지고 역순으로 추적해야 됩니다

[ㄹ(123.213)]

저도 자세히는 안봤는데 저걸 implement한게 링크의 내용물인것 같네요