Beakjoon] Ax+By=C (백준 21568코테) - 정수론 (C++)
🅰️문제주소 : https://www.acmicpc.net/problem/21568 21568번: Ax+By=C A, B, C가 주어졌을 때, Ax+By=C를 만족하는 (x, y)중에서 다음을 만족하는 것을 아무거나 찾아보자. x, y는 정수 -1,000,000,000 ≤ x, y ≤ 1,000,000,000 www.acmicpc.net 🚩문제 🪡풀이 - ax+by = c 의 방정식의 해를 구하기 위해서는 확장 유클리드 호제법을 호제법을 사용해야 한다 - c % gcd(a,b) == 0 인 경우에만 정수해를 가지므로 먼저 체크 - 유클리드 호제법을 수행하되 x와 y의 이전값을 가지고 역순으로 계산하며 답을 찾아낼 수 있다 - x는 y', y는 x'-y'*q를 역순으로 계산한다. (이때 x' 는 x의 이전..
