{"id":34368,"date":"2024-11-01T09:27:21","date_gmt":"2024-11-01T09:27:21","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34368"},"modified":"2024-11-01T10:57:31","modified_gmt":"2024-11-01T10:57:31","slug":"c-coding-test-course-extended-euclidean-algorithm-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34368\/","title":{"rendered":"C++ Coding Test Course, Extended Euclidean Algorithm"},"content":{"rendered":"<article>\n<section>\n<h2>Introduction<\/h2>\n<p>\n            In modern development environments, various algorithms are necessary to solve numerous problems. Among them, algorithms that utilize mathematical techniques, particularly the \u201cExtended Euclidean Algorithm,\u201d are very useful tools. In this course, we will deeply explore the theory of the Extended Euclidean Algorithm and problems that frequently appear in coding tests. Through this content, you will systematically understand the Extended Euclidean Algorithm and develop the ability to solve practical problems using C++.\n        <\/p>\n<\/section>\n<section>\n<h2>What is the Extended Euclidean Algorithm?<\/h2>\n<p>\n            The Euclidean Algorithm is an algorithm for finding the greatest common divisor (GCD) of two integers a and b. The Extended Euclidean Algorithm goes a step further by finding integers x and y that express the GCD of a and b as a linear combination of a and b.\n        <\/p>\n<p>\n            Mathematically, this can be expressed as follows:\n        <\/p>\n<p>\n<code>gcd(a, b) = ax + by<\/code>\n<\/p>\n<p>\n            Here, x and y are integers, and gcd(a, b) represents the greatest common divisor of a and b.\n        <\/p>\n<h3>Necessity of the Extended Euclidean Algorithm<\/h3>\n<p>\n            The Extended Euclidean Algorithm is mainly needed to solve problems such as:\n        <\/p>\n<ul>\n<li>Calculating modular multiplicative inverses<\/li>\n<li>Solve linear Diophantine equations<\/li>\n<li>Applications in cryptographic algorithms and hash algorithms<\/li>\n<\/ul>\n<\/section>\n<section>\n<h2>Problem Definition<\/h2>\n<p>\n            Now, let\u2019s define an algorithmic problem utilizing the Extended Euclidean Algorithm. The problem is as follows:\n        <\/p>\n<blockquote><p>\n            Given two integers a and b, find their greatest common divisor along with integers x and y that represent a and b as a linear combination.\n        <\/p><\/blockquote>\n<p>\n            For example, for a = 30 and b = 21, the greatest common divisor is 3, and it can be expressed as a linear combination of 30 and 21 as follows:\n        <\/p>\n<p>\n<code>3 = 1 * 30 + (-1) * 21<\/code>\n<\/p>\n<\/section>\n<section>\n<h2>Problem Solving Process<\/h2>\n<h3>1. Algorithm Design<\/h3>\n<p>\n            The basic idea of the Extended Euclidean Algorithm is to extend the Euclidean Algorithm to calculate the GCD along with the required x and y. The algorithm can be designed in the following manner:\n        <\/p>\n<ol>\n<li>Recursively call the function to calculate x and y values along with the GCD.<\/li>\n<li>Set up the following relationship using the two numbers a and b:<br \/>\n<blockquote><p>\n<code>gcd(a, b) = gcd(b, a % b)<\/code>\n<\/p><\/blockquote>\n<\/li>\n<li>As a base case, when b is 0, gcd(a, 0) = a and set x=1, y=0.<\/li>\n<li>After the recursive call, update x and y to obtain the linear combination.<\/li>\n<\/ol>\n<h3>2. C++ Implementation<\/h3>\n<p>\n            Here is the code implementing the above algorithm in C++:\n        <\/p>\n<pre><code class=\"language-cpp\">\n#include &lt;iostream&gt;\n\nusing namespace std;\n\n\/\/ Extended Euclidean Algorithm\nint extended_gcd(int a, int b, int &amp;x, int &amp;y) {\n    \/\/ Base case\n    if (b == 0) {\n        x = 1;\n        y = 0;\n        return a;\n    }\n    \n    int x1, y1; \/\/ Values after recursive call\n    int gcd = extended_gcd(b, a % b, x1, y1);\n    \n    \/\/ Update x and y\n    x = y1;\n    y = x1 - (a \/ b) * y1;\n    \n    return gcd;\n}\n\nint main() {\n    int a, b;\n    int x, y;\n    \n    cout &lt;&lt; \"Enter two numbers (a b): \";\n    cin &gt;&gt; a &gt;&gt; b;\n    \n    int gcd = extended_gcd(a, b, x, y);\n    \n    cout &lt;&lt; \"Greatest Common Divisor: \" &lt;&lt; gcd &lt;&lt; endl;\n    cout &lt;&lt; \"x: \" &lt;&lt; x &lt;&lt;, \" y: \" &lt;&lt; y &lt;&lt; endl;\n    \n    return 0;\n}\n        <\/code><\/pre>\n<h3>3. Code Explanation<\/h3>\n<p>\n            The above code implements the Extended Euclidean Algorithm to return the greatest common divisor along with x and y for the given two numbers a and b.\n        <\/p>\n<ul>\n<li><code>extended_gcd function<\/code>: Takes two numbers and x, y as parameters and calculates the GCD along with x and y values.<\/li>\n<li><code>main function<\/code>: Receives input from the user for two numbers, calls the <code>extended_gcd<\/code> function, and outputs the results.<\/li>\n<\/ul>\n<\/section>\n<section>\n<h2>Test Cases<\/h2>\n<p>\n            To test the implemented algorithm, let\u2019s use several test cases. For example:\n        <\/p>\n<table>\n<thead>\n<tr>\n<th>a<\/th>\n<th>b<\/th>\n<th>Greatest Common Divisor (GCD)<\/th>\n<th>x<\/th>\n<th>y<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>30<\/td>\n<td>21<\/td>\n<td>3<\/td>\n<td>1<\/td>\n<td>-1<\/td>\n<\/tr>\n<tr>\n<td>48<\/td>\n<td>18<\/td>\n<td>6<\/td>\n<td>1<\/td>\n<td>-2<\/td>\n<\/tr>\n<tr>\n<td>56<\/td>\n<td>15<\/td>\n<td>1<\/td>\n<td>-2<\/td>\n<td>7<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/section>\n<section>\n<h2>Conclusion<\/h2>\n<p>\n            In this course, we explored the theory of the Extended Euclidean Algorithm along with the problem-solving process using C++. The Extended Euclidean Algorithm is not only used for finding the greatest common divisor but is also widely applicable to solving various mathematical problems. Based on this fundamental theory, I hope you develop the ability to tackle more complex algorithmic problems.\n        <\/p>\n<\/section>\n<\/article>\n","protected":false},"excerpt":{"rendered":"<p>Introduction In modern development environments, various algorithms are necessary to solve numerous problems. Among them, algorithms that utilize mathematical techniques, particularly the \u201cExtended Euclidean Algorithm,\u201d are very useful tools. In this course, we will deeply explore the theory of the Extended Euclidean Algorithm and problems that frequently appear in coding tests. Through this content, you &hellip; <a href=\"https:\/\/atmokpo.com\/w\/34368\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;C++ Coding Test Course, Extended Euclidean Algorithm&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[111],"tags":[],"class_list":["post-34368","post","type-post","status-publish","format-standard","hentry","category-c-coding-test-tutorials-2"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>C++ Coding Test Course, Extended Euclidean Algorithm - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/34368\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"C++ Coding Test Course, Extended Euclidean Algorithm - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Introduction In modern development environments, various algorithms are necessary to solve numerous problems. Among them, algorithms that utilize mathematical techniques, particularly the \u201cExtended Euclidean Algorithm,\u201d are very useful tools. In this course, we will deeply explore the theory of the Extended Euclidean Algorithm and problems that frequently appear in coding tests. Through this content, you &hellip; \ub354 \ubcf4\uae30 &quot;C++ Coding Test Course, Extended Euclidean Algorithm&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34368\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:27:21+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T10:57:31+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"3\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34368\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34368\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"C++ Coding Test Course, Extended Euclidean Algorithm\",\"datePublished\":\"2024-11-01T09:27:21+00:00\",\"dateModified\":\"2024-11-01T10:57:31+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34368\/\"},\"wordCount\":515,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"C++ Coding Test Tutorials\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34368\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34368\/\",\"name\":\"C++ Coding Test Course, Extended Euclidean Algorithm - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:27:21+00:00\",\"dateModified\":\"2024-11-01T10:57:31+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34368\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34368\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34368\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"C++ Coding Test Course, Extended Euclidean Algorithm\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"C++ Coding Test Course, Extended Euclidean Algorithm - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/34368\/","og_locale":"ko_KR","og_type":"article","og_title":"C++ Coding Test Course, Extended Euclidean Algorithm - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Introduction In modern development environments, various algorithms are necessary to solve numerous problems. Among them, algorithms that utilize mathematical techniques, particularly the \u201cExtended Euclidean Algorithm,\u201d are very useful tools. In this course, we will deeply explore the theory of the Extended Euclidean Algorithm and problems that frequently appear in coding tests. Through this content, you &hellip; \ub354 \ubcf4\uae30 \"C++ Coding Test Course, Extended Euclidean Algorithm\"","og_url":"https:\/\/atmokpo.com\/w\/34368\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:27:21+00:00","article_modified_time":"2024-11-01T10:57:31+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"3\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34368\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34368\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"C++ Coding Test Course, Extended Euclidean Algorithm","datePublished":"2024-11-01T09:27:21+00:00","dateModified":"2024-11-01T10:57:31+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34368\/"},"wordCount":515,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["C++ Coding Test Tutorials"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34368\/","url":"https:\/\/atmokpo.com\/w\/34368\/","name":"C++ Coding Test Course, Extended Euclidean Algorithm - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:27:21+00:00","dateModified":"2024-11-01T10:57:31+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34368\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34368\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34368\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"C++ Coding Test Course, Extended Euclidean Algorithm"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34368","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=34368"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34368\/revisions"}],"predecessor-version":[{"id":34369,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34368\/revisions\/34369"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34368"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34368"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34368"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}