백준 15712번: 등비수열

www.acmicpc.net/problem/15712

15712번: 등비수열

---

등비수열의 합은 $ a+ar+ar^{2}+\cdots+ar^{n-1} $ 입니다.

 

이는 a로 묶어보면 $ a\left ( 1+r+r^{2}+\cdots+r^{n-1} \right ) $ 입니다.

 

조금 뜬금없지만 이 행렬을 관찰하면,

 

$ \begin{pmatrix} r & 0 \\ a & 1 \end{pmatrix} $

 

이 사실을 발견할 수 있습니다.

 

$ \begin{pmatrix} r^{2} & 0 \\ a\left ( r+1 \right ) & 1 \end{pmatrix} = \begin{pmatrix} r & 0 \\ a & 1 \end{pmatrix}^{2} $

 

같은 행렬을 한 번 더 곱하게 되면,

 

$ \begin{pmatrix} r^{3} & 0 \\ a\left ( r^{2}+r+1 \right ) & 1 \end{pmatrix} = \begin{pmatrix} r & 0 \\ a & 1 \end{pmatrix}^{3} $ 이 나옵니다.

 

즉, 이런 성질을 발견할 수 있습니다.

 

$ \begin{pmatrix} r^{n} & 0 \\ a\left ( r^{n-1}+\cdots+r+1 \right ) & 1 \end{pmatrix} = \begin{pmatrix} r & 0 \\ a & 1 \end{pmatrix}^{n} $

 

그러므로 우리는 어떤 행렬을 n제곱 해야 문제의 정답을 도출할 수 있을 지 알 수 있었습니다.

 

구현한 코드는 다음과 같습니다.

 

#include <stdio.h>

typedef struct {
	long long array[2][2];
} Matrix;

Matrix matrix_multiply_modular (Matrix A, Matrix B, long long M);
Matrix matrix_power_modular (Matrix A, long long K, long long M);

int main() {
	
	long long a, r, n, mod;
	scanf("%lld %lld %lld %lld", &a, &r, &n, &mod);
	
	Matrix Base;
	Base.array[0][0] = r, Base.array[0][1] = 0, Base.array[1][0] = a, Base.array[1][1] = 1;
	
	Base = matrix_power_modular (Base, n, mod);
	
	printf("%lld", Base.array[1][0]);
	
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B, long long M) {
	Matrix result;
	int i, j, k;
	for (i = 0; i < 2; i++) {
		for (j = 0; j < 2; j++) {
			result.array[i][j] = 0;
			for (k = 0; k < 2; k++) {
				long long temp = (A.array[i][k] * B.array[k][j]) % M;
				result.array[i][j] = (result.array[i][j] + temp) % M;
			}
		}
	}
	return result;
}

Matrix matrix_power_modular (Matrix A, long long K, long long M) {
	Matrix result;
	result.array[0][0] = result.array[1][1] = 1;
	result.array[0][1] = result.array[1][0] = 0;
	while (K > 0) {
		if (K & 1) {
			result = matrix_multiply_modular(result, A, M);
		}
		A = matrix_multiply_modular(A, A, M);
		K >>= 1;
	}
	return result;
}

 

(C11, 1116KB, 0ms, 제출번호 25772793)

---

처음에는, $ \left ( r-1 \right )^{-1} $ 의 mod 값을 구하려했는데

 

페르마의 소정리나 오일러 정리를 쓰기 어려운 환경이므로 생각을 바꾼 게 유효했습니다.