백준 15712번(등비수열)[C/C++]

🔗링크

1. 문제 풀이

처음엔 그냥 등비수열 합 공식으로 풀면 되겠네 히히 쉽다 하고 풀려 했지만
생각해보니 등비수열의 합공식은 분수형태이고
M이 소수라는 조건 없이는 페르마의 소정리를 적용할 수 없기에 좀더 고민해 보았다.

우선 첫 항인 a를 배제하고 등비가 r인 1~n까지 항의 합은
$\displaystyle\sum_{i=0}^{n -1}r^i = r^0+r^1+r^2...+r^{n - 1}$
이다.

등비가 r인 1~4까지의 수열은
$\displaystyle\sum_{i=0}^{3}r^i = r^0+r^1+r^2+r^{3}$
이다.

이 수식을 정리해보면
$r^0+r^1+r^2+r^{3} = r^0+r^1+r^2(r^0+r^1) = (r^0+r^1)(1 +r^2)$
이다.

여기서 $r^0 +r^1 = \displaystyle\sum_{i=0}^{1}r^i$ 임으로
위의 식은 다시
$\displaystyle\sum_{i=0}^{3}r^i =\displaystyle\sum_{i=0}^{1}r^i + r^2\displaystyle\sum_{i=0}^{1}r^i =(1 + r^2)\displaystyle\sum_{i=0}^{1}r^i$

이러한 형태로 정리 가능하다.

또한 n이 5라면 아래와 같은 식이 된다.
$\displaystyle\sum_{i=0}^{4}r^i =(1 + r^2)\displaystyle\sum_{i=0}^{1}r^i + r^4$

즉 $S_{1,n}$이 (1-1)~(n-1)까지의 등비수열 합이라면
$S_{1,4} = S_{1,2} +S_{3,4} = S_{1,2} +r^2S_{1,2}$
$S_{1,5} = S_{1,2} +S_{3,4} +S_{5,5}= S_{1,2} + r^2S_{1,2} + r^4$
이 형태로 나타낼 수 있다.

위의 식들을 정리하여 점화식을 구한다면
n이 짝수일 경우
$S_{1,n} = S_{1,n/2} +S_{n/2 + 1,n} = S_{1,n/2} +r^{n/2}(S_{1,n/2}) = (1+r^{n/2})S_{1,n/2}$

n이 홀수일 경우
$S_{1,n} = (1+r^{(n-1)/2})S_{1,(n-1)/2} + r^n$

이제 이러한 점화식을 적용하여 코드를 작성하면 문제를 풀수 있다.

2. 코드

#include<stdio.h>
typedef long long ll;
ll a, r, n, m, res;

ll pow(ll r, ll n) {
	if (n == 1)return r % m;
	if (n == 0)return 1;
	if (n % 2)return ((r % m) * pow(r, n - 1)) % m;
	else {
		ll tmp;
		tmp = pow(r, n / 2);
		return (tmp * tmp) % m;
	}
}

ll f(ll r,ll n) {
	if (n == 1)return 1;
	if (n % 2)return ((f(r, n / 2) * (1 + pow(r, n / 2))) % m + pow(r, n - 1)) % m;
	else return (f(r, n / 2) * (1 + pow(r, n / 2))) % m;
	
}

int main() {
	scanf("%lld %lld %lld %lld", &a, &r, &n, &m);
	printf("%lld", (a * f(r, n)) % m);
	return 0;
}

3. 후기

항상 가장 작은 문제부터 시작하는 버릇을 가지자,,