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

---

🅰️문제주소 : https://www.acmicpc.net/problem/21568

21568번: Ax+By=C

 

🚩문제 

 

 

🪡풀이 

 - 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;
}

 

💡알게 된 것 

 - 확장 유클리드 호제법을 이용하여 방정식을 푸는 방법

---