백준 30988 - sqrt(f(x)) 풀이

문제 링크: 백준 30988 - $\sqrt{f(x)}$

Prologue

이 문제는 깡수학 문제입니다. 지금 이 글을 쓰고 있는 2024년 9월 10일 기준으로 제출수가 96, 맞힌사람 수가 20밖에 안되는 문제이므로 이 글을 보고계시다면 저처럼 수학을 좋아하시거나 독특한 분이시겠네요.

저는 이 문제를 풀기 위해서 한 3시간 정도를 쓴 것 같습니다. 백준문제를 풀기 위해 노트에다가 수식을 적고 전개하는건 처음이었는데 신선한 경험이었습니다.

Problem Analysis

$g(g(x))=f(x)$을 만족하는 다항식을 $f(x)$의 제곱근이라고 한답니다. 제한 조건을 보니 $f(x)$의 차수 $n$이 $1 \le n \le 25$입니다.

흠.. 만약 $n=7$이라고 해봅시다. $g(g(x))$의 최고차항이 $7$이 나올 수 있긴 할까요? 문제를 살펴보다보면 어렵지 않게 다음과 같은 사실을 알 수 있습니다.

$g(x)$는 $n$이 제곱수일 때만 존재한다.

---

$g(x)$의 차수를 $m$이라 하자.

$g(x)=O(x^m) \\ \ \\ g(g(x))=O(O(x^m)^m) \\ \ \\ =O(x^{m^2})=O(x^n)$

$m^2=n$이므로 $n$이 제곱수가 아니면 $g(x)$는 존재하지 않는다.

좋습니다. 그럼 $m=1,2,3,4,5(n=1,4,9,16,25)$일 때만 조사하면 되겠네요! 하지만 $g(x)$의 계수가 $-100 \le b_i \le 100$이므로 브루트포스를 돌리면 최악의 경우 $O(201^5)$라 이것만으로는 쉽지 않을것 같습니다.

좀 더 식을 전개해볼까요?

에서 $g(g(x))$는

입니다.

저희는 계수 비교법을 통해 $b_i$들을 하나씩 찾아나갈 것입니다. 그런데 이 모든 항을 싹 다 전개하고 다시 맞추는 건 너무 고된 노동이므로 트릭을 사용하겠습니다. 저희는 $g(g(x))$의 첫번째 항만 이용하여 계수비교를 할 것입니다.

글로 쓰니까 트릭이 쉽사리 와닿지 않네요. 예시를 들어 설명하겠습니다.

$g(x)=b_2x^2+b_1x+b_0$이라고 해봅시다. 그럼 $g(g(x))$는

$g(g(x))=b_2(b_2x^2+b_1x+b_0)^2+b_1(b_2x^2+b_1x+b_0)+b_0$

가 됩니다. 그리고

$f(x)=g(g(x))=8 x^4 - 8 x^3 +8 x^2 - 3x + 2$

라고 둡시다. 여기서 다음의 질문들에 대답해보겠습니다.


Q1: $b_2$의 값은 얼마인가요?
최고차항 $x^4$의 계수를 비교해봅시다. $x^4$는 $g(g(x))$의 첫 번째 항 $b_2(b_2x^2+b_1x+b_0)^2$에서 등장하고 최고차항의 계수는 $b_2$로만 이루어져 있으므로 구하기 간편합니다. 즉, $b_2^3x^4=8x^4$에서 $b_2=2$입니다. 쉽네요.

Q2: $b_1$의 값은 얼마인가요?
$x^3$의 계수를 비교해봅시다. $x^3$는 $g(g(x))$의 첫 번째 항 $b_2(b_2x^2+b_1x+b_0)^2$에서 $x$과 $x^2$를 곱해서 만들 수 있습니다. $x \times x^2$과 $x^2 \times x$ 두 가지 방법이 있으므로 $2b_2^2b_1x^3=-8x^3$입니다. 아까 $b_2$를 구해놨고, $x^3$의 계수는 $b_2$와 $b_1$만으로 구성되어있으므로 $b_1$을 하나로 결정할 수 있습니다. 따라서 $2(2)^2b_1=-8$에서 $b_1=-1$입니다.

Q3: $b_0$의 값은 얼마인가요?
$x^2$의 계수를 비교해봅시다. $x^2$는 $g(g(x))$의 첫 번ㅉ.. 어? 이제는 두 번째 항도 고려해야 합니다. $x^2$는 $g(g(x))$의 첫 번째 항과 두 번째 항 두 곳에서 나올 수 있기 때문입니다. 심지어 $x^2$는 첫 번째 항에서 3가지의 방법으로 나올 수 있습니다. 좀 귀찮은데요. 어차피 $b_0$ 하나밖에 안남았고 $b_i$의 범위는 고작 201밖에 안되니 브루트포스로 구하는게 정신건강에 좋을 것 같습니다.

위 예시를 보면 제가 무슨 소리를 하는지 감을 잡으셨을 거라고 생각합니다. 저는 $g(g(x))$의 첫번째 항, 즉,

만 이용하여 $b_i$를 결정한 뒤 나머지는 브루트포스를 돌리는 방식으로 알고리즘을 구상했습니다.

Determining $b_m$

의 최고차항 $x^{m^2}$의 계수는 다음과 같은 방법으로 구할 수 있습니다.

$x^{m^2}$의 계수

---

$g(g(x))$의 첫 번째 항에서

• $b_mx^m$을 $m$번 선택하여 구할 수 있다.
  $\binom{m}{0}(b_mx^m)^m$

따라서 $x^{m^2}$ 항은 위 식에 $b_m$을 곱한

입니다. 이 항이 $f(x)$의 최고차항 $a_nx^n$과 동일한지 보기 위해 $g(g(x))$의 두 번째 항이 언제 $x^{m^2}$의 계수에 영향을 주게 되는지 확인해보죠.

는 $m>0$일 때 성립하므로 모든 자연수 $m$에 대해 $b_m^{m+1}=a_n$입니다.

$m>0$일 때,

$b_m^{m+1}=a_n$

Determining $b_{m-1}$

의 $x^{m^2-1}$의 계수는 다음과 같은 방법으로 구할 수 있습니다.

$x^{m^2-1}$의 계수

---

$g(g(x))$의 첫 번째 항에서

• $b_mx^m$을 $m-1$번 선택하고 $b_{m-1}x^{m-1}$을 $1$번 선택하여 구할 수 있다.
  $\binom{m}{1}(b_mx^m)^{m-1}(b_{m-1}x^{m-1})$

따라서 $x^{m^2-1}$ 항은 위 식에 $b_m$을 곱한

입니다. 이 항이 $f(x)$의 항 $a_{n-1}x^{n-1}$과 동일한지 보기 위해 $g(g(x))$의 두 번째 항이 언제 $x^{m^2-1}$의 계수에 영향을 주게 되는지 확인해보죠.

는 $m>1$일 때 성립하므로 $1$보다 큰 자연수 $m$에 대해 $mb_m^mb_{m-1}=a_{n-1}$입니다.

$m>1$일 때,

$mb_m^mb_{m-1}=a_{n-1}$

$m=1$일 때,
어차피 이게 마지막 항이므로 브루트포스를 돌린다.

Determining $b_{m-2}$

의 $x^{m^2-2}$의 계수는 다음과 같은 방법으로 구할 수 있습니다.

$x^{m^2-2}$의 계수

---

$g(g(x))$의 첫 번째 항에서

• $b_mx^m$을 $m-1$번 선택하고 $b_{m-2}x^{m-2}$을 $1$번 선택하여 구할 수 있다.
  $\binom{m}{1}(b_mx^m)^{m-1}(b_{m-2}x^{m-2})$
  
  
• $b_mx^m$을 $m-2$번 선택하고 $b_{m-1}x^{m-1}$을 $2$번 선택하여 구할 수 있다.
  $\binom{m}{2}(b_mx^m)^{m-2}(b_{m-1}x^{m-1})^2$

따라서 $x^{m^2-2}$ 항은 위 식들을 다 더하고 $b_m$을 곱한

입니다. 이 항이 $f(x)$의 항 $a_{n-2}x^{n-2}$과 동일한지 보기 위해 $g(g(x))$의 두 번째 항이 언제 $x^{m^2-2}$의 계수에 영향을 주게 되는지 확인해보죠.

는 $m>2$일 때 성립하므로 $2$보다 큰 자연수 $m$에 대해 $mb_m^mb_{m-2}+\frac{m(m-1)}{2}b_m^{m-1}b_{m-1}^2=a_{n-2}$입니다.

$m>2$일 때,

$mb_m^mb_{m-2}+\frac{m(m-1)}{2}b_m^{m-1}b_{m-1}^2=a_{n-2}$

$m=2$일 때,
어차피 이게 마지막 항이므로 브루트포스를 돌린다.

Determining $b_{m-3}$

의 $x^{m^2-3}$의 계수는 다음과 같은 방법으로 구할 수 있습니다.

$x^{m^2-3}$의 계수

---

$g(g(x))$의 첫 번째 항에서

• $b_mx^m$을 $m-1$번 선택하고 $b_{m-3}x^{m-3}$을 $1$번 선택하여 구할 수 있다.
  $\binom{m}{1}(b_mx^m)^{m-1}(b_{m-3}x^{m-3})$
  
  
• $b_mx^m$을 $m-2$번 선택하고 $b_{m-1}x^{m-1}$을 $1$번, $b_{m-2}x^{m-2}$을 1번 선택하여 구할 수 있다.
  $m(m-1)(b_mx^m)^{m-2}(b_{m-1}x^{m-1})(b_{m-2}x^{m-2})$
  *$\binom{m}{2}$이 아니라 $m(m-1)$인 이유는 같은 것을 두 번 선택하는 것이 아니기 때문이다.
  
  
• $b_mx^m$을 $m-3$번 선택하고 $b_{m-1}x^{m-1}$을 $3$번 선택하여 구할 수 있다.
  $\binom{m}{3}(b_mx^m)^{m-3}(b_{m-1}x^{m-1})^3$

따라서 $x^{m^2-3}$ 항은 위 식들을 다 더하고 $b_m$을 곱한

입니다. 이 항이 $f(x)$의 항 $a_{n-3}x^{n-3}$과 동일한지 보기 위해 $g(g(x))$의 두 번째 항이 언제 $x^{m^2-3}$의 계수에 영향을 주게 되는지 확인해보죠.

는 $m>3$일 때 성립하므로 $3$보다 큰 자연수 $m$에 대해 $mb_m^mb_{m-3} + m(m-1)b_m^{m-1}b_{m-1}b_{m-2} + \frac{m(m-1)(m-2)}{3!}b_m^{m-2}b_{m-1}^3=a_{n-3}$입니다.

$m>3$일 때,

$mb_m^mb_{m-3} + m(m-1)b_m^{m-1}b_{m-1}b_{m-2} + \frac{m(m-1)(m-2)}{3!}b_m^{m-2}b_{m-1}^3=a_{n-3}$

$m=3$일 때,
어차피 이게 마지막 항이므로 브루트포스를 돌린다.

Determining $b_{m-4}$

의 $x^{m^2-4}$의 계수는 다음과 같은 방법으로 구할 수 있습니다.

$x^{m^2-4}$의 계수

---

$g(g(x))$의 첫 번째 항에서

• $b_mx^m$을 $m-1$번 선택하고 $b_{m-4}x^{m-4}$을 $1$번 선택하여 구할 수 있다.
  $\binom{m}{1}(b_mx^m)^{m-1}(b_{m-4}x^{m-4})$
  
  
• $b_mx^m$을 $m-2$번 선택하고 $b_{m-2}x^{m-2}$을 $2$번 선택하여 구할 수 있다.
  $\binom{m}{2}(b_mx^m)^{m-2}(b_{m-2}x^{m-2})^2$
  
  
• $b_mx^m$을 $m-2$번 선택하고 $b_{m-1}x^{m-1}$을 $1$번, $b_{m-3}x^{m-3}$을 $1$번 선택하여 구할 수 있다.
  $m(m-1)(b_mx^m)^{m-2}(b_{m-1}x^{m-1})(b_{m-3}x^{m-3})$
  
  
• $b_mx^m$을 $m-3$번 선택하고 $b_{m-1}x^{m-1}$을 $2$번, $b_{m-2}x^{m-2}$을 $1$번 선택하여 구할 수 있다.
  $\binom{m}{2}(m-2)(b_mx^m)^{m-3}(b_{m-1}x^{m-1})^2(b_{m-2}x^{m-2})$
  
  
• $b_mx^m$을 $m-4$번 선택하고 $b_{m-1}x^{m-1}$을 $4$번 선택하여 구할 수 있다.
  $\binom{m}{4}(b_mx^m)^{m-4}(b_{m-1}x^{m-1})^4$

따라서 $x^{m^2-4}$ 항은 위 식들을 다 더하고 $b_m$을 곱한

입니다. 이 항이 $f(x)$의 항 $a_{n-4}x^{n-4}$과 동일한지 보기 위해 $g(g(x))$의 두 번째 항이 언제 $x^{m^2-4}$의 계수에 영향을 주게 되는지 확인해보죠.

는 $m>4$일 때 성립하므로 $4$보다 큰 자연수 $m$에 대해 $mb_m^mb_{m-4}+\frac{m(m-1)}{2}b_m^{m-1}b_{m-2}^2+m(m-1)b_m^{m-1}b_{m-1}b_{m-3}+\frac{m(m-1)}{2}(m-2)b_m^{m-2}b_{m-1}^2b_{m-2}+\frac{m(m-1)(m-2)(m-3)}{4!}b_m^{m-3}b_{m-1}^4=a_{n-4}$입니다.

$m>4$일 때,

$mb_m^mb_{m-4}+\frac{m(m-1)}{2}b_m^{m-1}b_{m-2}^2+m(m-1)b_m^{m-1}b_{m-1}b_{m-3}+\frac{m(m-1)}{2}(m-2)b_m^{m-2}b_{m-1}^2b_{m-2}+\frac{m(m-1)(m-2)(m-3)}{4!}b_m^{m-3}b_{m-1}^4=a_{n-4}$

$m=4$일 때,
어차피 이게 마지막 항이므로 브루트포스를 돌린다.

Code

Long Version

def e():print(-1);exit()

def function_mul(l,n,r,t,p): #제곱하는 method. 곱할 리스트, 제곱할 수, 결과 리스트, 누적곱, position
    if n==0:
        r[p]+=t
        return
    for x in range(len(l)):function_mul(l,n-1,r,l[x]*t,p+x)
    return r

def function_com(a): #함수합성하는 method. 입력은 오름차순 계수
    t=len(a)-1
    r=[0]*t*t+[0]
    for x in range(t,0,-1):
        s=function_mul(a,x,[0]*t*x+[0],1,0)
        s=[0]*(t*t+1-len(s))+s
        for y in range(t*t+1):
            r[y]+=a[t-x]*s[y]
    r[-1]+=a[-1]
    return r

def check(t):
    if function_com(t)==a:
        print(m)
        print(*t)
        exit()


n=int(input())
a=[*map(int,input().split())]
if n not in[1,4,9,16,25]:e()
m=int(n**.5)


#b0 결정
B0=[]
for b0 in range(-100,101):
    if b0**(m+1)==a[0]:B0.append(b0)
if B0==[]:e()

if m==1:
    for b0 in B0:
        for b1 in range(-100,101):
            check([b0,b1])
    e()


#b1 결정
B1=[]
for b0 in B0:
    for b1 in range(-100,101):
        if m*b0**m*b1==a[1]:
            B1.append([b0,b1])
if B1==[]:e()

if m==2:
    for b0,b1 in B1:
        for b2 in range(-100,101):
            check([b0,b1,b2])
    e()


#b2 결정
B2=[]
for b0,b1 in B1:
    for b2 in range(-100,101):
        if m*b0**m*b2+m*(m-1)//2*b0**(m-1)*b1**2==a[2]:
            B2.append([b0,b1,b2])
if B2==[]:e()

if m==3:
    for b0,b1,b2 in B2:
        for b3 in range(-100,101):
            check([b0,b1,b2,b3])
    e()


#b3 결정
B3=[]
for b0,b1,b2 in B2:
    for b3 in range(-100,101):
        if m*b0**m*b3+m*(m-1)*b0**(m-1)*b1*b2+m*(m-1)*(m-2)//6*b0**(m-2)*b1**3==a[3]:
            B3.append([b0,b1,b2,b3])
if B3==[]:e()

if m==4:
    for b0,b1,b2,b3 in B3:
        for b4 in range(-100,101):
            check([b0,b1,b2,b3,b4])
    e()


#b4 결정
B4=[]
for b0,b1,b2,b3 in B3:
    for b4 in range(-100,101):
        if m*b0**m*b4+m*(m-1)//2*b0**(m-1)*b2**2+m*(m-1)*b0**(m-1)*b1*b3+m*(m-1)//2*(m-2)*b0**(m-2)*b1**2*b2+m*(m-1)*(m-2)*(m-3)//24*b0**(m-3)*b1**4==a[4]:
            B4.append([b0,b1,b2,b3,b4])
if B4==[]:e()

for b0,b1,b2,b3,b4 in B4:
    for b5 in range(-100,101):
        check([b0,b1,b2,b3,b4,b5])
e()

function_mul은 제곱을 전개하는 함수이고 function_com은 합성함수를 출력하는 함수입니다. function_com은 $g(x)$를 인풋으로 받으면 $g(g(x))$를 수행해 출력하는 함수라고 보시면 됩니다.

$g(x)=b_mx^m+\cdots+b_1x+b_0$에서 $b_m,\cdots,b_1$까지는 다 정해진 상태에서 $b_0$을 브루트포싱할 때 function_com이 호출되어 return 결과가 $f(x)$과 일치하는지 확인합니다. 다만, 합성함수를 구하는 함수가 상당히 무거우므로 $m=5$일 때 $201^2$번의 호출은 시간초과가 납니다. 이것이 제가 굳이 $b_{m-4}$까지를 위에서 하나씩 다 구한 이유입니다.

Short Version

def e(*x):print(*x);exit()

def function_mul(l,n,r,t,p):
    if n==0:r[p]+=t;return
    for x in range(len(l)):function_mul(l,n-1,r,l[x]*t,p+x)
    return r

def function_com(a):
    t=len(a)-1
    r=[0]*t*t+[0]
    for x in range(t,0,-1):
        s=function_mul(a,x,[0]*t*x+[0],1,0)
        s=[0]*(t*t+1-len(s))+s
        for y in range(t*t+1):r[y]+=a[t-x]*s[y]
    r[-1]+=a[-1]
    return r

n=int(input())
a=[*map(int,input().split())]
if n not in[1,4,9,16,25]:e(-1)
m=int(n**.5)

l=['y**(m+1)',
   'y*m*b[0]**m',
   'b[0]*(m*(m-1)//2*b[1]**2*b[0]**(m-2)+m*y*b[0]**(m-1))',
   'm*b[0]**m*y+m*(m-1)*b[0]**(m-1)*b[1]*b[2]+m*(m-1)*(m-2)//6*b[0]**(m-2)*b[1]**3',
   'b[0]**5*y*5+b[0]**4*(10*b[2]**2+b[1]*b[3]*20)+b[0]**3*b[1]**2*b[2]*30+b[0]**2*b[1]**4*5']
P=[[]]
for x in range(5):
    B=[]
    for b in P:
        for y in range(-100,101):
            if eval(l[x])==a[x]:B.append(b+[y])
    if B==[]:e(-1)
    for t in B:
        for y in range(-100,101):
            if function_com(t+[y])==a:e(m,*t,y)
    P=B

단순하게 Long Version에서 반복되는 부분을 합친 것 뿐입니다. Long Version이 더 알아보기 쉽기 때문에 Long Version과 Short Version을 따로 첨부합니다.

Test Case Generating Code

def function_mul(l,n,r,t,p): #제곱하는 method. 곱할 리스트, 제곱할 수, 결과 리스트, 누적곱, position
    if n==0:
        r[p]+=t
        return
    for x in range(len(l)):function_mul(l,n-1,r,l[x]*t,p+x)
    return r

def function_com(a): #함수합성하는 method. 입력은 오름차순 계수
    t=len(a)-1
    r=[0]*t*t+[0]
    for x in range(t,0,-1):
        s=function_mul(a,x,[0]*t*x+[0],1,0)
        s=[0]*(t*t+1-len(s))+s
        for y in range(t*t+1):
            r[y]+=a[t-x]*s[y]
    r[-1]+=a[-1]
    return r

from pyperclip import copy
from keyboard import is_pressed
from random import randint
from time import sleep

m=5 #차수
for x in range(5): #테케 개수
    r=[randint(-100,100)]
    for y in range(m):r.append(randint(-100,100))
    l=function_com(r)
    for x in [l,r]:
        if x==l:s=str(m*m)
        else:s=str(m)
        s+='\n'
        for y in x:s+=str(y)+' '
        copy(s)
        while not is_pressed('v'):pass
        sleep(0.5)

이 코드로 테스트케이스를 직접 만드실 수 있습니다. 변수 m을 조정하여 $g(x)$의 차수를 결정한 후 프로그램을 실행한 뒤 ctrl+v를 반복해서 누르시면 차례대로 테케 1번의 인풋, 아웃풋, 테케 2번의 인풋, 아웃풋, ... 이 붙여넣기 뒵니다.

Epilogue

하하... 지금봐도 저 어마무시한 식을 전개한게 놀라울 따름이네요. 여러분은 저처럼 이상한 문제 푸시지 말고 다른 좋은 문제들 푸시길 바랍니다.