3955번: 캔디분배

3955번: 캔디분배 - 선형 다오판토스 방정식, 확장 유클리드 알고리즘

구매하고 싶은 캔디는 K*X+1개이며 사탕 한 봉지에 사탕이 C개 들어있을 때 몇 봉지를 사야할 지 묻는 문제이다.

이 때 이를 수식으로 적어보면 K*X+1 = C*N가 되며 이 수식을 만족하는 10^9이 넘지 않는 N을 구해주면 된다.

K*X+1 = C*N는 C*N - K*X = 1로 변환 될 수 있다. 이 형태는 일차부정방정식의 형태로,

먼저 선형 다오판토스 방정식에 의하여 일차부정방정식 ax + by = c이고 d = gcd(a, b)라 할 때

d | c 즉 c를 d로 나누었을 때 나누어떨어지지 않는다면 해가 존재하지 않으며,

그렇지 않다면 해가 무수히 존재하며 이 수식을 만족하는 하나의 특수 해를 구한다면 일반 해를 구해낼 수 있다.

그렇기에 먼저 C*N - K*X = 1에서 c는 1이므로 해를 갖기 위해서는 gcd(C, K) = 1이여야함을 알 수 있으며

특수 해를 구하기 위해 확장 유클리드 알고리즘을 사용한다.

확장 유클리드 알고리즘은 임의의 정수 a와 b에 대하여

ax + by = gcd(a, b)를 만족하는 정수 x, y가 항상 존재한다이며 이 때의 x, y를 구할 수 있다.

그러나 이 때의 x, y는 자연수 해가 아닌 정수 해이기에 일반 해를 구하는 공식을 이용하여

두 값이 자연수가 될 때까지 특정 작업을 진행해주며 이 일반해가 10^9이하일 경우 바로 N을 출력해주면 된다.