[백준] 21568번 : Ax+By=C C++ 문제풀이 솔루션

 

문제

A, B, C가 주어졌을 때, Ax+By=C를 만족하는 (x, y)중에서 다음을 만족하는 것을 아무거나 찾아보자.

• x, y는 정수
• -1,000,000,000 ≤ x, y ≤ 1,000,000,000

입력

첫째 줄에 정수 A, B, C가 주어진다.

출력

Ax+By=C를 만족하는 x, y를 공백으로 구분해 출력한다. 문제의 조건을 만족하는 (x, y)가 존재하지 않는 경우에는 -1을 출력한다.

제한

• -1,000,000 ≤ A, B, C ≤ 1,000,000
• A, B ≠ 0

 

 

확장 유클리드 호제법을 사용하는 문제입니다.

ax+by=c 를 ax+by=1로 놓겠습니다.

c가 a와 b의 배수인 경우에만 방정식의 해를 가집니다.

최대 공약수를 구할 때 처럼 유클리드 호제법을 반복 사용합니다. 이때 몫을 기록합니다.

반복으로 구한 몫을 이용하여 x=y' y=x'-y'*q 를 계산합니다.

이때 q는 몫이고 x' y'는 각 이전 x와 y값 입니다.

몫이 0인 최초값까지 계산 하면 x와 y의 값이 구해집니다.

처음 방정식의 결과 값을 1로 생각했으므로, c를 a와 b의 최대공약수로 나눈 값을 x와 y에 곱해주면 방정식의 해를 구할 수 있습니다.

이는 유클리드 호제법을 역순으로 반복하는 과정과 동일합니다.

따라서 gcd 함수를 반복 사용하면 더 깔끔하게 코드를 작성할 수 있습니다.

#include <iostream>
#include <stack>
#include <algorithm>

#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false)

using namespace std;

int ansx, ansy;
stack<int> expgcd; //몫
int gcd(int a, int b) {
  int r = a % b;
  expgcd.push(a / b);
  if (r == 0) return b;
  else return gcd(b, r);
}
void cal(int a, int b) {
  int x = b;
  int share = expgcd.top();
  if (share == 0) return;
  expgcd.pop();
  int y = a - b * share;
  ansx = y;
  ansy = x;
  cal(x, y);
}
int main() {
  fast_io;
  int a, b, c;
  cin >> a >> b >> c;
  long long temp = gcd(a, b);
  if (c % temp != 0) {
	cout << -1;
	return 0;
  }
  expgcd = stack<int>();
  gcd(a, b);
  cal(1, 0);
  cout << ansx * c / temp << ' ' << ansy * c / temp;
  return 0;
}