(์ ํด๋ฆฌ๋) ํธ์ ๋ฒ(Euclidean Algorithm)๋ ์ ์์ ์ต๋๊ณต์ฝ์(gcd; Greatest Common Divisor)๋ฅผ ์ฝ๊ฒ ์์๋ด๋ ๋ฐฉ๋ฒgcd(0, A) = A๋ชจ๋ ์๋ 0์ ๋๋ ์ ์๋ค. ๋ฐ๋ผ์, 0์ ๋ชจ๋ ์ฝ์๋ ์์์ ์ ์ A๋ฅผ ํฌํจํ๋ค. ๋ฐ๋ผ์, ๋์ gcd๋ A๊ฐ ๋๋ค. gcd(a,b) = gcd(b, a%b) (๋จ, a > b) -- b > a์ด๋ฉด ๊ฐ์ ๋ฐ๊พผ๋ค cf. ๊ท๋ฅ๋ฒ์ด๋ค ๋ช ์ ๊ฐ ์ฐธ์์ ์ง์ ์ฆ๋ช ํ๋ ๋์ , ๊ทธ ๋ถ์ ๋ช ์ ๊ฐ ์ฐธ์ด๋ผ๊ณ ๊ฐ์ ํ์ฌ ๊ทธ๊ฒ์ ๋ถํฉ๋ฆฌ์ฑ์ ์ฆ๋ช ํจ์ผ๋ก์จ ์๋์ ๋ช ์ ๊ฐ ์ฐธ์ธ ๊ฒ์ ๋ณด์ฌ ์ฃผ๋ ๊ฐ์ ์ฆ๋ช ๋ฒ. [๋ค์ด๋ฒ์ฌ์ ]import java.io.BufferedReader;import java.io.IOException;import java.io.InputS..
