BOJ 28242 - 수학 선생님의 고민(Hard)

BOJ 28242 - 수학 선생님의 고민(Hard)

일단 판별식을 갈겨서 $b^2-4ac \ge 0$ 이고 제곱수인지 확인한다.

그런다음 근의 공식을 쓰면 $p,q=\dfrac{-b \pm \sqrt{ b^2-4ac }}{2a}$ 가 되는데,

그럼 $nx^2+(n+1)x-(n+2)=n(x-p)(x-q)$ 가 가능한지에 대해 봐야한다.

그럼 $-p$와 $-q$가 정수가 되기위해 곱해져야 할 수를 각각 $p', q'$ 라고 하자.

$p'=\dfrac{2n}{gcd(b-\sqrt{ b^2-4ac }, 2a)}$ 이다.

$p'q' \mid n$ 이라면 답이 있고 그렇지 않다면 답이 없다.

답이 있다면 이제 $n$을 적절히 분배하여 $a, b$에 $p'$ 를 곱해주고 $c,d$에 $\dfrac{n}{p'}$ 를 곱해주면 된다.

void solve() {
   int n;
   cin >> n;
   int a = n, b = n + 1, c = -(n + 2);

   int d = b * b - 4 * a * c;
   if (d < 0) {
      cout << -1;
      return;
   }
   int dd = sqrt(d);
   if (dd * dd != d) {
      cout << -1;
      return;
   }

   int p1 = -b + dd, q1 = -b - dd;
   int g1 = gcd(p1, 2 * a), g2 = gcd(q1, 2 * a);
   p1 /= g1, q1 /= g2;
   int p2 = 2 * a / g1, q2 = 2 * a / g2;
   if (n % (p2 * q2) != 0) {
      cout << -1;
      return;
   }
   int A = p2;
   int B = -p1;
   n /= p2;
   int C = n;
   int D = -q1 * n / q2;

   cout << A << ' ' << B << ' ' << C << ' ' << D;
}

쉬운 풀이

여담으로 이 문제는 $n$이 작아 $\sqrt{ n } \cdot \sqrt{ n+2 }$ 개의 조합으로 $a, b$ 를 결정해주고 풀 수 있다.

왜냐면 $ac=n$ 이고 $bd=-(n+2)$ 이기 때문에 $\text{Min}(a,c) \le \sqrt{ n }$ 처럼 되기 때문이다.

$nx^2+(n+1)x-(n+2)=(ax+b)(cx+d)$ 에서

$a, b$를 결정해준다면 $c=n/a, d=-(n+2)/b$ 가 된다.

이때, $b,d$ 의 부호가 다르게 되는 두 가지 경우를 검사해준다.