백준 11661번: 해의 개수

자기 전에 한 문제만 풀고 자려고 했는데, 이 문제 때문에 잠을 못잤다. 케이스가 상당히 극악인 문제이다.

문제는 아주 심플하다. 방정식 Ax + By + C = 0의 정수해의 개수 구하기이다.

x와 y는 x1 ≤ x ≤ x2, y1 ≤ y ≤ y2를 만족해야 한다.

각 수의 범위는 -10^8 ~ 10^8이다.

일단 수의 범위가 상당히 크기 때문에 직접 다 해보는 알고리즘은 시간초과가 뜰 가능성이 농후하다.

케이스를 나누어가며 접근해보자.

i) A와 B 둘 다 0인 경우

가장 쉬운 경우이다. C = 0이면 모든 해가 정답이고, C ≠ 0이면 해가 없다.

ii) A와 B 둘 중 하나만 0인 경우

편의상 A = 0, B ≠ 0이라 해보자.

그럴 경우 방정식은 By + C = 0이 된다. C가 B로 나누어 떨어지고, 그 해가 y1 ≤ y ≤ y2을 만족할 경우 해가 존재하며, 이 때 x는 어떤 수가 와도 된다.

iii) A와 B 둘 다 0이 아닌 경우

대망의 케이스이다.

이를 풀기 위해서는 약간의 정수론적 배경지식이 필요하다.

먼저, ax + by = c가 정수해 (x, y)를 가지려면 gcd(a, b) | c를 만족해야 한다. 만족하지 않으면 해가 존재하지 않는다.

만족하는 경우에는 어떻게 풀어야 할까?

gcd(a, b) = d라 하자. 그러면 a = da', b = db'로 나타낼 수 있다.

이 경우, 만약 하나의 해 (x0, y0)를 찾아낼 수 있다면 모든 해는 다음과 같은 꼴로 나타낼 수 있다.

x = x0 + b'k, y = y0 - a'k (k는 임의의 정수)

그렇다면 관건은, 하나의 해 (x0, y0)를 찾아내는 것이다.

다행히, 이를 만족하는 해를 찾아내는 방법이 있다. 다들 한 번쯤은 들어봤을 유클리드 호제법을 역이용하면 된다.

유클리드 호제법을 역이용하면, ax + by = d (d는 gcd(a, b))를 만족하는 x, y를 찾아낼 수 있다.

d | c를 만족하므로, 이를 통해 찾아낸 (x, y)에 c / d를 곱하면 최종적으로 우리가 원하는 (x0, y0)를 찾아낼 수 있다.

유클리드 호제법을 통해 알아내는 방법은 다음과 같다.

예시로, 324x + 118y = 8을 만족하는 x, y를 찾아보자.

먼저 gcd(324, 118) = 2 | 8이므로 해가 존재한다.

유클리드 호제법을 통해 gcd를 구하면,

324 = 118 * 2 + 88

118 = 88 * 1 + 30

88 = 30 * 2 + 28

30 = 28 * 1 + 2

28 = 2 * 14 (끝)

로 gcd를 찾아낼 수 있다. 이제 거꾸로 가보자.

2 = 30 - 28

2 = 30 - (88 - 30 * 2) = 30 * 3 - 88

2 = (118 - 88) * 3 - 88 = 118 * 3 - 88 * 4

2 = 118 * 3 - (324 - 118 * 2) * 4 = 118 * 11 - 324 * 4

x = -4, y = 11라는 해를 찾았다.

이제 양변에 4를 곱하면

324 * (-16) + 118 * 44 = 8이 성립하므로, (x0, y0) = (-16, 44)임을 알 수 있다.

이제 한 가지 해를 찾았으니 k의 범위를 확인해주자.

x1 ≤ x0 + b'k ≤ x2라는 등식으로부터 k의 범위를 찾아낼 수 있다. y도 마찬가지로 하면 된다.

x, y로부터 얻은 두 개의 범위에 모두 포함되는 k의 갯수를 세면 답이 나온다.

여기까지가 풀이이다. 이 과정을 오류없이 잘 구현하면 맞았습니다! 메시지를 볼 수 있다..^^

중간에 몇 가지 유의사항을 살펴보면, 음수의 나눗셈에 유의해야 하고(https://jeonggyun.tistory.com/228) 숫자의 범위에 유의해야 한다.

예컨데 유클리드 알고리즘을 통해 구한 x0와 y0가 꼭 정수 범위라는 보장은 없다.

푸는 데 너무 오래 걸려서 억울해서 코드는 안올릴까 하다가 나같은 시행착오를 겪는 사람이 없기를 바라는 마음에서 올린다. 코드가 조금 난잡하다.. ㅎㅎ

11661.cpp