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

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

---

문제 풀이

폴라드 로, 정수론

 

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

 

1. $A=0$인 경우

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

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

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

 

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

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

 

1-3. $B\ne 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\ne 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\ne 0$, $C\ne 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\ne 0$인 경우

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

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

 

코드

	from math import gcd
	from random import *
	import sys
	input = sys.stdin.readline
	prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41] # n < 2^64
	def miller_rabin(n, p):
	if n%p == 0: return True
	d = n-1
	while d%2==0: d >>= 1
	temp = pow(p, d, n)
	if temp == 1 or temp == n-1: return True
	while d*2 < n-1:
	d *= 2
	if pow(p, d, n) == n-1: return True
	return False
	def prime_chk(n):
	# for i in range(3): # 2^32
	# if n == prime[i]: return True
	# if not miller_rabin(n, prime[i]): return False
	# return True
	for i in range(13): # 2^64
	if n == prime[i]: return True
	if not miller_rabin(n, prime[i]): return False
	return True
	def pollard_rho(n):
	if prime_chk(n): return n
	if n == 1: return 1
	a = b = randint(2, n)
	c, d = randint(1, n), 1
	while True:
	a = ((a*a)%n+c%n)%n
	for _ in range(2): b = ((b*b)%n+c%n)%n
	d = gcd(abs(a-b), n)
	if d == n: return pollard_rho(n)
	if d != 1: break
	if prime_chk(d): return d
	else: return pollard_rho(d)
	A, B, C, D = map(int, input().split())
	if A == 0:
	if B != 0 and C != 0:
	x = gcd(B, C)
	if -D%x == 0: print("INFINITY")
	else: print(0)
	elif B == 0 and C != 0:
	if -D%C == 0: print("INFINITY")
	else: print(0)
	elif B != 0 and C == 0:
	if -D%B == 0: print("INFINITY")
	else: print(0)
	else:
	if D == 0: print("INFINITY")
	else: print(0)
	else:
	if B == 0 and C == 0:
	if D == 0: print("INFINITY")
	else:
	if D%A == 0:
	nn = n = -D//A
	n = abs(n)
	frac = {}
	while n % 2 == 0:
	n //= 2
	if 2 in frac: frac[2] += 1
	else: frac[2] = 1
	while n > 1:
	div = pollard_rho(n)
	if div in frac: frac[div] += 1
	else: frac[div] = 1
	n //= div
	divs = [1]
	for pr, exp in frac.items():
	new_divs = []
	for d in divs:
	for i in range(1, exp+1):
	new_divs.append(d*(pr**i))
	divs.extend(new_divs)
	ans = []
	for i in divs:
	ans.append((-i, -nn//i))
	ans.append((i, nn//i))
	print(len(ans))
	for i in sorted(ans):
	print(*i)
	else:
	print(0)
	else:
	if B*C == A*D:
	if C%A == 0: print("INFINITY")
	elif B%A == 0: print("INFINITY")
	else: print(0)
	else:
	x = n = B*C-A*D
	n = abs(n)
	frac = {}
	while n % 2 == 0:
	n //= 2
	if 2 in frac: frac[2] += 1
	else: frac[2] = 1
	while n > 1:
	div = pollard_rho(n)
	if div in frac: frac[div] += 1
	else: frac[div] = 1
	n //= div
	divs = [1]
	for pr, exp in frac.items():
	new_divs = []
	for d in divs:
	for i in range(1, exp+1):
	new_divs.append(d*(pr**i))
	divs.extend(new_divs)
	ddivs = []
	for i in divs:
	ddivs.append((i, x//i))
	ddivs.append((-i, x//(-i)))
	ans = []
	for i, j in ddivs:
	if (i-C)%A == 0 and (j-B)%A == 0:
	ans.append(((i-C)//A, (j-B)//A))
	print(len(ans))
	for i in sorted(ans):
	print(*i)

view raw 32242.py hosted with ❤ by GitHub