<div id="readability-page-1" class="page">
                
                
                


<div id="wrap">
	
	<hr>
	<section>
		
		<article id="content">
			

			

			

			

			<div>
				

				            
                
	
	
		<div>
			<p>운동하는 개발자/알고리즘, 코딩테스트</p>
			
			<p>
				<span>2024. 1. 1. 20:25</span>
				
			</p>
		</div>
		<div><hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style5">
<h3 data-ke-size="size23"><br>🅰️문제주소 :<span> <a href="https://www.acmicpc.net/problem/21568" target="_blank" rel="noopener&nbsp;noreferrer">https://www.acmicpc.net/problem/21568</a></span></h3>
<figure id="og_1704107949868" contenteditable="false" data-ke-type="opengraph" data-ke-align="alignCenter" data-og-type="website" data-og-title="21568번: Ax+By=C" data-og-description="A, B, C가 주어졌을 때, Ax+By=C를 만족하는 (x, y)중에서 다음을 만족하는 것을 아무거나 찾아보자. x, y는 정수 -1,000,000,000 ≤ x, y ≤ 1,000,000,000" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/21568" data-og-url="https://www.acmicpc.net/problem/21568" data-og-image="https://scrap.kakaocdn.net/dn/erbCuI/hyUXMZdqE7/d3pcj6vpcTL3FsUqlkcfNK/img.png?width=2834&amp;height=1480&amp;face=0_0_2834_1480"><a href="https://www.acmicpc.net/problem/21568" target="_blank" rel="noopener" data-source-url="https://www.acmicpc.net/problem/21568">

<div>
<p data-ke-size="size16">21568번: Ax+By=C</p>
<p data-ke-size="size16">A, B, C가 주어졌을 때, Ax+By=C를 만족하는 (x, y)중에서 다음을 만족하는 것을 아무거나 찾아보자. x, y는 정수 -1,000,000,000 ≤ x, y ≤ 1,000,000,000</p>
<p data-ke-size="size16">www.acmicpc.net</p>
</div>
</a><img src="https://scrap.kakaocdn.net/dn/erbCuI/hyUXMZdqE7/d3pcj6vpcTL3FsUqlkcfNK/img.png?width=2834&amp;height=1480&amp;face=0_0_2834_1480"></figure>

<h3 data-ke-size="size23"><br>🚩문제&nbsp;</h3>
<figure data-ke-mobilestyle="widthOrigin" data-origin-width="629" data-origin-height="165"><span data-url="https://blog.kakaocdn.net/dn/bUW2aN/btsCX7z7KE1/Q7jQEiIjktXrtKh5KdQtR1/img.png" data-lightbox="lightbox"><img src="https://blog.kakaocdn.net/dn/bUW2aN/btsCX7z7KE1/Q7jQEiIjktXrtKh5KdQtR1/img.png" onerror="this.onerror=null; this.src='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png'; this.srcset='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png';" data-origin-width="629" data-origin-height="165"></span></figure>



<h3 data-ke-size="size23">🪡풀이&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- ax+by = c 의 방정식의 해를 구하기 위해서는 확장 유클리드 호제법을 호제법을 사용해야 한다<br>&nbsp;- c % gcd(a,b) == 0 인 경우에만 정수해를 가지므로 먼저 체크<br>&nbsp;- 유클리드 호제법을 수행하되 x와 y의 이전값을 가지고 역순으로 계산하며 답을 찾아낼 수 있다<br>&nbsp;- x는 y', y는 x'-y'*q를 역순으로 계산한다. (이때 x' 는 x의 이전값, y'는 y의 이전값, q는 몫이다.<br>&nbsp;- 역순으로 수행시 최초의 x'와 y'의 값은 없으므로 각각 1과 0으로 지정하고 진행하면 된다</p>


<h3 data-ke-size="size23">☕코드는 아래 숨김</h3>
<div data-text-less="닫기" data-text-more="더보기" data-ke-type="moreLess"><p><a>더보기</a></p><div>
<pre id="code_1701091944942" data-ke-language="cpp" data-ke-type="codeblock"><code>#include &lt;iostream&gt;
#include &lt;vector&gt;

int gcd(int a, int b) {
	if (b == 0)
		return a;
	else {
		return gcd(b, a % b);
	}
}

std::vector&lt;int&gt; Execute(int a, int b) {
	std::vector&lt;int&gt; ret(2);

	if (b == 0) {
		ret[0] = 1;
		ret[1] = 0;
		return ret;
	}
	int q = a / b;
	std::vector&lt;int&gt; v = Execute(b, a % b);
	ret[0] = v[1];
	ret[1] = v[0] - v[1] * q;
	return ret;
}


int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);

	int A, B, C;

	std::cin &gt;&gt; A &gt;&gt; B &gt;&gt; C;

	int gcd_val = gcd(A, B);

	if (C % gcd_val != 0) {
		std::cout &lt;&lt; "-1";
		return 0;
	}

	int mok = C / gcd_val;

	std::vector&lt;int&gt; ret = Execute(A, B);
	std::cout &lt;&lt; ret[0] * mok &lt;&lt; " " &lt;&lt; ret[1] * mok;

	return 0;
}</code></pre>
</div>
</div>

<h3 data-ke-size="size23">💡알게 된 것&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- 확장 유클리드 호제법을 이용하여 방정식을 푸는 방법</p>
<hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style5">
</div>
		

		
			<div>
				<h2><strong>'운동하는 개발자/알고리즘, 코딩테스트'</strong> Related Articles</h2>
				
			</div>
		

		



	

                
            
			</div>

			

			

			

		</article>
	</section>
	<hr>
	
	
</div>







                




        
        











  


        

                
                







                
                


                

</div>

운동하는 개발자

️문제주소 : https://www.acmicpc.net/problem/21568
 
 문제 
 
 
 풀이 
 - ax+by = c 의 방정식의 해를 구하기 위해서는 확장 유클리드 호제법을 호제법을 사용해야 한다
 - c % gcd(a,b) == 0 인 경우에만 정수해를 가지므로 먼저 체크
 - 유클리드 호제법을 수행하되 x와 y의 이전값을 가지고 역순으로 계산하며 답을 찾아낼 수 있다
 - x는 y', y는 x'-y'*q를 역순으로 계산한다. (이때 x' 는 x의 이전값, y'는 y의 이전값, q는 몫이다.
 - 역순으로 수행시 최초의 x'와 y'의 값은 없으므로 각각 1과 0으로 지정하고 진행하면 된다
 
 
☕코드는 아래 숨김
더보기
#include <iostream>
#include <vector>
int gcd(int a, int b) {
	if (b == 0)
		return a;
	else {
		return gcd(b, a % b);
	}
}
std::vector<int> Execute(int a, int b) {
	std::vector<int> ret(2);
	if (b == 0) {
		ret[0] = 1;
		ret[1] = 0;
		return ret;
	}
	int q = a / b;
	std::vector<int> v = Execute(b, a % b);
	ret[0] = v[1];
	ret[1] = v[0] - v[1] * q;
	return ret;
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int A, B, C;
	std::cin >> A >> B >> C;
	int gcd_val = gcd(A, B);
	if (C % gcd_val != 0) {
		std::cout << "-1";
		return 0;
	}
	int mok = C / gcd_val;
	std::vector<int> ret = Execute(A, B);
	std::cout << ret[0] * mok << " " << ret[1] * mok;
	return 0;
}
 
 알게 된 것 
 - 확장 유클리드 호제법을 이용하여 방정식을 푸는 방법
 
            
'운동하는 개발자 > 알고리즘, 코딩테스트' 카테고리의 다른 글
Beakjoon] 최소공배수 (백준 1934코테) - 정수론 (C++)  (0)
2023.12.28
Beakjoon] GCD(n, k) = 1 aka.오일러의 피 (백준 11689 코테) - 정수론 (C++)  (0)
2023.12.25
Beakjoon] 제곱 ㄴㄴ 수 (백준 1016 코테) - 정수론 (C++)  (0)
2023.12.21
Beakjoon] 소수 구하기 (백준 1929 코테) - 정수론 (C++)  (0)
2023.12.16
Beakjoon] 수 묶기 (백준 1744 코테) - 그리디  (0)
2023.12.14

Beakjoon] Ax+By=C (백준 21568코테) - 정수론 (C++)

댓글