곱셈 (2) 썸네일형 리스트형 백준 10830 행렬 제곱 - 파이썬 문제. 풀이. 분할정복의 제곱거듭 공식과 행렬의 공식을 합쳐서 풀면 된다. 지수가 짝 수이면 n^(지수/2) * n^(지수/2), 지수가 홀 수 이면 n^(지수/2) * n^(지수/2) * n 이런 방식으로 풀면 된다. 소스코드. import sys def Square(b): if b == 1: return matrix temp = Square(b // 2) if b % 2 == 0: result = matrix_multiple(temp,temp) return result elif b % 2 == 1: result = matrix_multiple(temp,temp) result = matrix_multiple(result, matrix) return result # 행렬 곱 def matrix_multi.. 백준 1629 곱셈 - 파이썬 문제. 풀이. 분할정복 알고리즘을 이용하여 지수가 짝수 일때는 n^(지수/2) * n^(지수/2) 를 해주면 되고 지수가 홀 수 일때는 n^((지수-1)/2) * n^((지수-1)/2) * n 을 해주면 된다. 시간이 빡빡하기 때문에 함수 호출을 한번만 이용하여한다. 소스코드. import sys def div_con(num, index): if index == 1: return num % C power = div_con(num, index//2) # 미리 값 구하기 if index%2 == 0: return power * power % C elif index%2 == 1: return power * power * num % C A, B, C = map(int, sys.stdin.readline().sp.. 이전 1 다음
