MingyuPark

문제 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 아이디어 https://park-mingyu.tistory.com/38 [백준 1629] 곱셈 문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 아이디어 $f(n)$을 $x^n$을 계산하 park-mingy..

문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 아이디어 $f(n)$을 $x^n$을 계산하기 위해 필요한 최소 계산 횟수라고 하자. $2^16$을 계산하기 위해 필요한 최소 계산 횟수를 구해보자. 직접 계산하면 2를 16번 곱해야 하기 때문에 16번의 계산이 필요하다. 이 경우 n이 2,147,483,647이 되면 계산 횟수가 너무 많아진다. 이럴 때 분할 정복을 이용한다. $f(16)$ = $f(8)+1$ : $2^{16} = 2^8 * 2^8$이기 때문 $f(8)$ = $f(4)+1$ : $2^{8}..