[BOJ] n제곱 계산 (12728, P1)

추천받은 수학 문제를 풀어 보았습니다. 구현의 난이도 보다는 수학 자체에 치중된 난이도로
수학 값으로 플래티넘1이 나온 것 같습니다.

 

1, 2차 시도 / 실패

처음 든 생각은, (3+루트5)^n을 계산해보면 되겠다는 생각이 들었습니다.

(a+b루트5)(3+루트5)를 계산한 뒤, 이를 행렬표현 하는 생각을 했고, 행렬의 거듭제곱이니, 수가 커지니 분할제곱 합니다.

수가 너무 커지므로 modulo...?       실패!

네, 실패한 사유는 정수 부분은 1000으로 나눠도 되겠지만 루트5는 무리수 파트임을 간과한 풀이로 실패했습니다.

그렇다고  modulo를 풀어주면 시간 초과로 실패입니다. 루트5를 확정적으로 없애줄 방법이 필요할 것 같습니다. 컴퓨터는 루트를 정확하게 계산 할 수 없을거니까요.

 

잘 왔지만, 조금 다른 방법이 필요합니다. 큰 틀이 바뀌지 않고 계산 방법만 바꿔주면 됩니다. 루트만 잘 없애면 해결될거 같습니다.

 

 

3차 시도 / 성공

아이디어는, 켤레근의 활용입니다. 3+루트5가 아닌, 3-루트5를 같이 활용합니다. 두 개는 서로 N제곱을 해도 루트5의 부호차이만 발생할 뿐, 나머지 파트는 모두 동일하게 나옵니다. (3-루트5)는 몇 제곱을 하던0과 1 사이의 값이겠네요.

그럼 근과 계수와의 관계를 통해 이차방정식을 얻고, 이를 점화식 형태로 확장 가능할 것입니다. 점화식은 행렬 표현이 되겠네요.

그럼, (3+루트5)^n + (3-루트5)^n의 값을 얻게 됩니다.  필요 없는 부분은 0~1 사이의 값이므로 저 값에서 1을 뺍니다.

 

최종 풀이를 얻기 위한 수학적 계산은 마저 직접 해 봅시다.

 

코드

# 켤레의 성질 + 점화식을 활용하는 대수적 문제.
# 켤레 끼리는 제곱해도 서로 더해서 상쇄가 된다. (사실 근과 계수와의 관계 확장...)
# 점화식을 행렬곱으로 변형하는 테크닉이 필요.
p = 1000
def matrix_prod(m1, m2, p):
    x1 = (m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % p
    x2 = (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % p
    x3 = (m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % p
    x4 = (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % p
    return [[x1, x2], [x3, x4]]
def matrix_power_mod_p(matrix, n, p):
    if n == 0:
        return [[1, 0], [0, 1]]  
    elif n == 1:
        return matrix
    else:
        temp = matrix_power_mod_p(matrix, n//2, p)
        if n % 2 == 0:
            return matrix_prod(temp, temp, p)
        else:
            return matrix_prod(matrix_prod(temp, temp, p), matrix, p)
matrix = [[6, 996], [1, 0]] # 6 -4 0 1 이나 modulo를 위해. 
t_case = int(input())
for T in range(1, t_case+1):
    N = int(input())    # 초항 두개는 0항부터 2, 6 
    result_matrix = matrix_power_mod_p(matrix, N - 1, p)
    answer = (result_matrix[0][0] * 6 + result_matrix[0][1] * 2) - 1
    answer = answer % 1000
    if answer == 0:
        ansert = '000'
    elif len(str(answer)) == 1:
        answer = '00' + str(answer)
    elif len(str(answer)) == 2:
        answer = '0' + str(answer)
    else:
        answer = str(answer)
    
    print("Case #%d: %s" %(T, answer))