빠른 거듭 제곱1 [BOJ] 백준 10830번: 행렬 제곱 (빠른 거듭 제곱) 먼저 우리는 빠른 거듭 제곱 알고리즘을 알고있습니다. pow(a,y), 즉 a^y 를 구할때 만약 y가 홀수면 a * a^y/2*a^y/2로 분해하여 짝수 거듭 제곱의 반을 구해가면서 O(lgY)의 복잡도로 구할 수 있습니다. int pow(int a, int y) { int x = 1; while (y) { if (y & 1) { x *= a; } a *= a; y /= 2; } return x; } math.h 헤더의 내장 pow를 사용하지 않고 직접 구현하여 쓰는 이유는, 몇몇 문제에서 특정 수로 나눈 나머지 값을 요구하기 때문입니다. 이유는 답이 너무 커지거나 하는 경우에, 보통 1,000,000,007 (1e9+7)와 같은 소수로 나눈 나머지 값을 요구합니다. 소수는 어떠한 수와도 나누어 떨어지.. 2020. 8. 17. 이전 1 다음