์ฑ [Do it! ์๊ณ ๋ฆฌ์ฆ ์ฝ๋ฉ ํ ์คํธ - ์๋ฐ ํธ;๊น์ข ๊ด ์ง์]์ ์ฐธ๊ณ ํ์ฌ ์์ฑํ์์ต๋๋ค. ์ด ๊ธ์ ์ฆ๋ช ๋ณด๋ค๋ ๋ฐฉ์ ์์ ํด๋ฅผ ๊ตฌํ ๋ ์ด๋ป๊ฒ ์ ๊ทผํด์ผ ํ๋์ง ์ค๋ช ํ๋ค.์ ํด๋ฆฌ๋ ํธ์ ๋ฒ์ด ๋ ์์ ์ต๋๊ณต์ฝ์๋ฅผ ๊ตฌํ๊ธฐ ์ํ ๊ฒ์ด๋ผ๊ณ ๋ณด๋ฉด, ํ์ฅ ์ ํด๋ฆฌ๋ ํธ์ ๋ฒ์ ๋ฐฉ์ ์์ ํด๋ฅผ ๊ตฌํ๋ ๊ฒ์ด๋ผ๊ณ ๋ณผ ์ ์๋ค. ์ด๋ฆ์์ ์ ์ ์๋ฏ์ด ํ์ฅ ์ ํด๋ฆฌ๋ ํธ์ ๋ฒ์ ๊ธฐ๋ณธ ํธ์ ๋ฒ์ ์๊ณ ์์ด์ผ ์งํ๋๋คax + by = c์ฃผ์ด์ง a, b, c, x, y๋ ๋ชจ๋ ์ ์๋ผ๊ณ ์๊ฐํ๋ค. ์ด๋ x, y์ ํด๋ c % gcd(a,b) = 0 ์กฐ๊ฑด์ด ์ฑ๋ฆฝ๋์ด์ผ ์ ์ํด๋ฅผ ๊ตฌํ ์ ์๋ค. ๊ทธ๋ ๊ธฐ ๋๋ฌธ์ ๋ฌธ์ ์ ์ ๊ทผํ ๋ ๋จผ์ c์ ๊ฐ์ด gcd(a,b)์ ๋ฐฐ์๊ฐ ๋ง๋์ง ํ์ธ๋ถํฐ ํด์ผ ํ๋ค. ๋ฐฐ์๊ฐ ๋ง๋ค๋ฉด ์ผ์ฐจ ์กฐ๊ฑด์ ๋ง์กฑํ ๊ฒ์ด๋ค. c๊ฐ g..
