[BOJ][Python] 백준 32242번 - $Axy+Bx+Cy+D=0$

문제 링크: https://www.acmicpc.net/problem/32242

---

문제 풀이

폴라드 로, 정수론

 

처음에는 서브테스크로 나눠서 생각을 해봤는데, $A$가 0이냐 0이 아니냐를 기준으로 나눠서 생각했다. 생각해야할 케이스가 매우 많으므로 천천히 생각해봐야 한다.

 

1. $A=0$인 경우

1-1. $B \neq 0$, $C \neq 0$ 인 경우

$Bx+Cy+D=0$의 형태가 되는데 베주 항등식이 떠오를 것이다. 정수 해가 무한히 존재하는 지 혹은 없는지에 대해 알 수 있다.

$GCD(B, C) = X$라 하고, 베주 항등식에 따르면 $X$가 $D$의 배수이면 정수인 $x, y$가 무수히 많기 때문에, 이를 판별해서 구하면 된다.

 

1-2. $B = 0$, $C \neq 0$ 인 경우

$Cy+D=0$이 되고, $y=-\frac{D}{C}$가 된다. 즉, $D$가 $C$의 배수라면 $y$의 정수 해는 $-\frac{D}{C}$이고 $x$는 무수히 많은 정수해가 있게 된다. 아니라면 정수해를 가지는 $x$, $y$는 없다.

 

1-3. $B \neq 0$, $C = 0$ 인 경우

$Bx+D=0$이 되고, $y=-\frac{D}{B}$가 된다. 즉, $D$가 $B$의 배수라면 $y$의 정수 해는 $-\frac{D}{B}$이고 $x$는 무수히 많은 정수 해가 있게 된다. 아니라면 정수 해를 가지는 $x$, $y$는 없다.

 

1-4. $B = 0$, $C = 0$ 인 경우

$D=0$이 되고, $D$가 0이라면, 정수 해를 가지는 $x$, $y$는 무수히 많고 0이 아니라면 정수 해를 가지는 $x$, $y$는 없다.

 

2. $A \neq 0$인 경우

2-1. $B = 0$, $C = 0$ 인 경우

$Axy+D=0$이 된다. 즉, $xy=-\frac{D}{A}$가 되는데 당연히 $D$는 $A$의 배수여야 정수 해를 가질 수 있다. 정수 해 $x, y$의 쌍을 구하기 위해서는 $-\frac{D}{A}$를 소인수분해 해서 쌍을 찾으면 된다.

$-\frac{D}{A}$의 값이 양수인 경우와 음수인 경우가 존재하는데 양수인 경우는 $x > 0, y > 0$와 $x < 0, y < 0$어야 하며, 음수인 경우는 $x < 0, y > 0$와 $x > 0, y < 0$이므로 케이스를 고려하여 정수 해를 구하자.

당연하겠지만 $D = 0$이면, $x$와 $y$ 둘 중에 0이면 0이 아닌 다른 변수는 정수 집합의 원소 모두에 포함될 수 있다. 여기서는 $-\frac{D}{A}$가 최대 $10^{9}$가 될 수 있다. $O(N^{1/2})$ 소인수분해도 충분히 돌 것이다.

 

2-2. $B \neq 0$, $C \neq 0$ 인 경우

이 문제의 가장 핵심인 문제인데, $Axy+Bx+Cy+D=0$을 변형하면 된다. 자세한 서술 없이 변형하면,

 

$Axy+Bx+Cy+D=0$

$A^{2}xy+ABx+ACy+AD=0$ => 양변에 $A$를 곱함.

$A^{2}xy+ABx+ACy=-AD$ => $AD$를 우변으로 옮김.

$(Ax+C)(Ay+B)-BC=-AD$ => $A$에 대한 이차방정식으로 변형.

$(Ax+C)(Ay+B)=BC-AD$ => $BC$를 우변으로 옮김.

 

가 된다. 여기서 알 수 있는 사실은 $BC-AD$를 잘 써먹으면 된다.

 

2-2-1. $BC-AD = 0$인 경우

$(Ax+C)$, $(Ay+B)$ 둘 중에 하나만 0이면 다른 한쪽의 경우 모든 정수 집합에 속한다.

$Ax+C = 0$을 변형하면 $x = -\frac{C}{A}$고, $Ay+B = 0$을 변형하면 $y = -\frac{B}{A}$이다.

즉 $C$가 $A$의 배수이거나, $B$가 $A$의 배수이면 해가 무수히 많고, 아니라면 없다.

 

2-2-2. $BC-AD \neq 0$인 경우

2-1의 경우와 다르지 않지만 조금 더 조건이 많은데, $(Ax+C)(Ay+B)=BC-AD$에서 $(Ax+C) = X'$, $(Ay+B) = Y'$라 하면, $X'Y' = BC-AD$다. $BC-AD$를 소인수분해 하여 정수 쌍을 찾아주면 된다. (이때 $X', Y'$가 유리수가 안되는 이유는 스스로 확인해보면 좋다.) 우리는 $X', Y'$의 쌍을 찾았으므로, $Ax+C = X'$를 변형하면 $x = \frac{X'-C}{A}$가 되고, $Ay+B = Y'$를 변형하면 $y = \frac{Y'-B}{A}$가 된다.

따라서 $X'-C$가 $A$의 배수이면서, $Y'-B$가 $A$의 배수여야 한다. 마찬가지로 $BC-AD$가 양수냐 음수냐를 확인해서 $X', Y'$의 쌍을 2개의 형태로 나타내어야 한다. $BC-AD$는 최대 $10^{18}$이므로, 폴라드 로 알고리즘을 사용하여 빠르게 소인수분해 하자.

 

코드