\uc548\ub155\ud558\uc138\uc694! \uc624\ub298\uc740 \uc218\ud559\uc801 \uc54c\uace0\ub9ac\uc998\uc758 \ud558\ub098\uc778 \ud655\uc7a5 \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95<\/strong>\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc54c\uace0\ub9ac\uc998 \uc2dc\ud5d8 \uc900\ube44\ub97c \uc704\ud55c \uc774 \uac15\uc88c\ub294, \uc54c\uace0\ub9ac\uc998\uc801 \uc0ac\uace0\ub97c \ubc14\ud0d5\uc73c\ub85c \ubb38\uc81c \ud480\uc774 \ubc29\ubc95\uc744 \uc790\uc138\ud788 \uc124\uba85\ud558\uba70, \uc2a4\uc704\ud504\ud2b8\ub85c \uad6c\ud604 \uac00\ub2a5\ud569\ub2c8\ub2e4.<\/p>\n \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc740 \ub450 \uc22b\uc790 \\(a\\)\uc640 \\(b\\)\uc758 \ucd5c\ub300\uacf5\uc57d\uc218(GCD)\ub97c \uad6c\ud558\ub294 \uace0\uc804\uc801\uc778 \uc54c\uace0\ub9ac\uc998\uc785\ub2c8\ub2e4. \uc774 \uacfc\uc815\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n \uc774 \uc2dd\uc740 \\(b\\)\uac00 0\uc774 \ub420 \ub54c\uae4c\uc9c0 \uacc4\uc18d\ud574\uc11c \ubc18\ubcf5\ub418\uba70, \\(GCD(a, 0) = a\\)\uac00 \uc131\ub9bd\ud569\ub2c8\ub2e4. \uc989, \ucd5c\uc885\uc801\uc73c\ub85c \uccab \ubc88\uc9f8 \uc778\uc790\uc5d0 \ub0a8\uc544\uc788\ub294 \uac12\uc774 \ub450 \uc218\uc758 GCD\uc785\ub2c8\ub2e4.<\/p>\n \ud655\uc7a5 \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc740 \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc744 \uae30\ubc18\uc73c\ub85c \ud558\uc5ec, \ub450 \uc815\uc218 \\(a\\)\uc640 \\(b\\)\uc5d0 \ub300\ud574 \ub2e4\uc74c\uc758 \uc2dd\uc744 \ucc3e\uc2b5\ub2c8\ub2e4:<\/p>\n \uc5ec\uae30\uc11c \\(x\\)\uc640 \\(y\\)\ub294 \uc815\uc218\uc774\uba70, \uc774\ub294 \uc77c\ubc18\uc801\uc73c\ub85c \ubca0\uc8fc \uc815\ub9ac(B\u00e9zout’s identity)\ub85c \uc54c\ub824\uc838 \uc788\uc2b5\ub2c8\ub2e4. \uc774 \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uba74 \uc8fc\uc5b4\uc9c4 \ub450 \uc22b\uc790\uc5d0 \ub300\ud55c GCD\ubfd0\ub9cc \uc544\ub2c8\ub77c, GCD\uc5d0 \ub300\ud55c \uacc4\uc218\ub3c4 \ucc3e\uc744 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n \uc774\uc81c \ud655\uc7a5 \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc744 \ud65c\uc6a9\ud558\uc5ec \ud574\uacb0\ud560 \uc218 \uc788\ub294 \ubb38\uc81c\ub97c \uc0b4\ud3b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4:<\/p>\n \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \uc8fc\uc5b4\uc9c4 \ub450 \uc218\uc758 GCD\ub97c \uad6c\ud558\uace0, \uadf8 GCD\ub97c \uad6c\ud558\uae30 \uc704\ud55c \uc120\ud615 \uc870\ud569 \uacc4\uc218 x\uc640 y\ub97c \ucc3e\uc544\uc57c \ud569\ub2c8\ub2e4. \uc774\ub97c \uc704\ud574 \ud655\uc7a5 \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc744 \uad6c\ud604\ud574\uc57c \ud569\ub2c8\ub2e4.<\/p>\n \uc774\uc81c \uc704 \uacfc\uc815\uc744 \ubc14\ud0d5\uc73c\ub85c \uc2a4\uc704\ud504\ud2b8 \ucf54\ub4dc\ub85c \uad6c\ud604\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4:<\/p>\n \uc704\uc758 \uc2a4\uc704\ud504\ud2b8 \ucf54\ub4dc\ub97c \uc0ac\uc6a9\ud558\uc5ec \uc8fc\uc5b4\uc9c4 \ubb38\uc81c\ub97c \ud480\uc5b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n \uc704\uc758 \uc785\ub825\uc5d0 \ub300\ud574, GCD\ub294 6\uc774\uba70, \\(30x + 12y = 6\\)\ub97c \ub9cc\uc871\uc2dc\ud0a4\uae30 \uc704\ud55c \\(x = 1\\)\uc640 \\(y = -2\\)\ub77c\ub294 \uc810\uc5d0\uc11c \ud655\uc778\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n \uc624\ub298\uc740 \ud655\uc7a5 \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uc558\uace0, \uc774\ub97c \ud1b5\ud574 \uc8fc\uc5b4\uc9c4 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ubc29\ubc95\uc744 \ubc30\uc6e0\uc2b5\ub2c8\ub2e4. \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \ucef4\ud4e8\ud130 \uacfc\ud559 \ubc0f \uc554\ud638\ud559\uc5d0\uc11c \uc911\uc694\ud55c \uc5ed\ud560\uc744 \ud569\ub2c8\ub2e4. \ub2e4\uc591\ud55c \uc751\uc6a9 \ud504\ub85c\uadf8\ub7a8\uc5d0\uc11c \ubc14\ub85c \ud6a8\uacfc\uc801\uc73c\ub85c \uc0ac\uc6a9\ud560 \uc218 \uc788\uc74c\uc744 \uc0c1\uae30\ud574 \uc8fc\uc138\uc694!<\/p>\n \uc55e\uc73c\ub85c\ub3c4 \uc54c\uace0\ub9ac\uc998 \uad00\ub828 \ub2e4\uc591\ud55c \uac15\uc88c\ub97c \ud1b5\ud574 \uc5ec\ub7ec\ubd84\uc758 \ucf54\ub529 \ub2a5\ub825\uc744 \ud0a4\uc6cc \ub098\uac00\uae30\ub97c \ubc14\ub78d\ub2c8\ub2e4. \uc9c8\ubb38\uc774\ub098 \ub354 \uc54c\uace0 \uc2f6\uc740 \ub0b4\uc6a9\uc774 \uc788\uc73c\uc2dc\uba74 \ub313\uae00 \ub0a8\uaca8\uc8fc\uc138\uc694!<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"1. \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc774\ub780?<\/h2>\n
GCD(a, b) = GCD(b, a % b)<\/code><\/pre>\n2. \ud655\uc7a5 \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc774\ub780?<\/h2>\n
ax + by = gcd(a, b)<\/code><\/pre>\n3. \ubb38\uc81c \uc124\uba85<\/h2>\n
\ubb38\uc81c: \uc8fc\uc5b4\uc9c4 \ub450 \uc815\uc218 a\uc640 b\uc5d0 \ub300\ud574, ax + by = gcd(a, b) \ub97c \ub9cc\uc871\ud558\ub294 x\uc640 y\ub97c \ucc3e\uc73c\uc2dc\uc624.<\/h3>\n
\uc785\ub825 \ud615\uc2dd<\/h3>\n
\n
\ucd9c\ub825 \ud615\uc2dd<\/h3>\n
\n
\uc608\uc81c \uc785\ub825<\/h3>\n
30 12<\/code><\/pre>\n\uc608\uc81c \ucd9c\ub825<\/h3>\n
6 1 -2<\/code><\/pre>\n4. \uc54c\uace0\ub9ac\uc998 \ud480\uc774 \uacfc\uc815<\/h2>\n
4.1. \ubb38\uc81c \ubd84\uc11d<\/h3>\n
4.2. \uc54c\uace0\ub9ac\uc998 \ud750\ub984\ub3c4<\/h3>\n
\n
4.3. \uc2a4\uc704\ud504\ud2b8 \uad6c\ud604<\/h3>\n
\nfunc extendedGCD(a: Int, b: Int) -> (gcd: Int, x: Int, y: Int) {\n if b == 0 {\n return (a, 1, 0)\n } else {\n let (gcd, x1, y1) = extendedGCD(a: b, b: a % b)\n let x = y1\n let y = x1 - (a \/ b) * y1\n return (gcd, x, y)\n }\n}\n\nfunc main() {\n let input = readLine()!.split(separator: \" \").map { Int($0)! }\n let a = input[0]\n let b = input[1]\n let (gcd, x, y) = extendedGCD(a: a, b: b)\n print(\"\\(gcd) \\(x) \\(y)\")\n}\n\n\/\/ \ud504\ub85c\uadf8\ub7a8 \uc2dc\uc791\uc810\nmain()\n<\/code><\/pre>\n5. \ubb38\uc81c \ud480\uc774 \uc608\uc2dc<\/h2>\n
\uc785\ub825<\/h3>\n
30 12<\/code><\/pre>\n\ucd9c\ub825<\/h3>\n
6 1 -2<\/code><\/pre>\n6. \uacb0\ub860<\/h2>\n