[백준 28242] 수학 선생님의 고민(Hard) (C++)

문제

---

이 문제는 수학 선생님의 고민(Easy)의 상위 문제이고, 수학 선생님의 고민(Easy)에 이 문제의 정답 코드를 제출하여 맞힐 수 있다.

차형준 선생님은 여느 때와 같이 재밌는 문제를 고민하다가 다음과 같이 양의 정수 𝑛에 대한 이차식 𝑛𝑥² + (𝑛 + 1)𝑥 − (𝑛 + 2)을 정수 범위에서 인수분해 하는 문제를 고안하게 되었다.

 𝑛이 작을 때에는 쉽게 손으로 계산할 수 있었지만, 𝑛이 커짐에 따라 문제는 버거워졌다.

따라서 선생님은 수학은 잘 못해도 시키는 대로 코딩은 하는 도훈이에게 문제를 맡겼다. 하지만 도훈이는 사실 ChatGPT가 알려준 코드를 복사-붙여넣기 해왔을 뿐이라 실상은 "Hello World!" 정도나 출력할 줄 안다. 그래서 도훈이는 늘 하던 대로 ChatGPT에게 코딩을 부탁했다.

하지만 답변 받는 도중 인터넷이 끊겨버렸다..!

 

ChatGPT에게 프로그램을 만들어달라고 하다가 인터넷이 끊긴 모습이다.

도훈이를 도와 𝑛𝑥² + (𝑛 + 1)𝑥 − (𝑛 + 2)를 정수 범위에서 인수분해 하는 프로그램을 작성하여라.

입력

---

첫 번째 줄에 양의 정수 𝑛이 주어진다.

 

출력

---

첫 번째 줄에 주어진 𝑛에 대해 이차식 𝑛𝑥² + (𝑛 + 1)𝑥 − (𝑛 + 2)가 정수 범위에서 인수분해가 불가능하다면 -1을 출력하고, 가능하다면 인수분해 한 결과를 나타내는 네 정수 𝑎, 𝑏, 𝑐, 𝑑를 공백으로 구분하여 출력한다. 이 네 정수는 (𝑎𝑥 + 𝑏)(𝑐𝑥 + 𝑑) = 𝑛𝑥² + (𝑛+1)𝑥 − (𝑛+2)임을 의미한다. 가능한 (𝑎,𝑏,𝑐,𝑑) 쌍이 여러 가지라면 그중 아무것이나 출력한다.

 

제한

---

•  1 ≤ 𝑛 ≤ 2×10⁶

 

문제 풀이

---

약수 판별과 브루트포스를 이용하는 문제.

 𝑛𝑥² + (𝑛+1)𝑥 − (𝑛+2)를 a, b ,c ,d 모두 양수인 인수분해 형식으로 변환하면 (𝑎𝑥 - 𝑏)(𝑐𝑥 + 𝑑)나 (𝑎𝑥 + 𝑏)(𝑐𝑥 - 𝑑)가 된다. 따라서 n은 ac, n+1은 ad-bc나 bc-ad, n+2는 bd가 된다. n과 n+2의 약수를 각각 구한 후 브루트포스로 a,b,c,d에 대입하며 ad-bc나 bc-ad가 n+1이 되는 네 정수 쌍이 있는지 확인하면 된다.

만약 ad-bc가 n+1이 된다면 (𝑎𝑥 - 𝑏)(𝑐𝑥 + 𝑑) (단, 네 정수는 모두 양수)이므로 실제 (𝑎,𝑏,𝑐,𝑑) 쌍 중 b가 음수이다. 출력할 때 구한 b값에 -를 붙여 출력한다.

만약 bc-ad가 n+1이 된다면 (𝑎𝑥 + 𝑏)(𝑐𝑥 - 𝑑) (단, 네 정수는 모두 양수)이므로 실제  (𝑎,𝑏,𝑐,𝑑) 쌍 중  d가 음수이다. 출력할 때 구한 d값에 -를 붙여 출력한다.

이외에도  a, b ,c ,d가 모두 양수인 인수 분해 형식 (-𝑎𝑥 - 𝑏)(-𝑐𝑥 + 𝑑)나 (-𝑎𝑥 + 𝑏)(-𝑐𝑥 - 𝑑)일 때  𝑛𝑥² + (𝑛+1)𝑥 − (𝑛+2)를 만족한다. 각각 n은 ac, n+1은 ad-bc나 bc-ad, n+2는 bd가 성립하므로, 위의 예시와 같이 풀어주면 된다.

 

아래는 코드.

#include <iostream>
#include <map>
#include <cmath>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	map<int, int> m1;
	map<int, int> m2;
	int a, b, c, d;
	bool canMake = false;
	for (int i = 1; i <= sqrt(N); i++)
	{
		if (N % i == 0)
		{
			m1.insert({ i, N / i });
		}
	}
	for (int i = 1; i <= sqrt(N+2); i++)
	{
		if ((N+2) % i == 0)
		{
			m2.insert({ i, (N+2) / i });
		}
	}
	for (map<int, int>::iterator it = m1.begin(); it != m1.end(); it++)
	{
		for (map<int, int>::iterator iter = m2.begin(); iter != m2.end() && canMake == false; iter++)
		{
			a = it->first;
			c = it->second;
			b = iter->first;
			d = iter->second;
			if (a * d - b * c == N + 1)
			{
				cout << a <<" " << -b <<" " << c <<" " << d << "\n";
				canMake = true;
				break;
			}
			else if (b * c - a * d == N + 1)
			{
				cout << a << " " << b << " " << c << " " << -d << "\n";
				canMake = true;
				break;
			}
		}
	}
	if (canMake == false)
	{
		cout << -1 << "\n";
	}
	return 0;
}