개요

이번엔 등비수열에 대해 공부해보자

등비수열 개념

등비수열은 각 항이 그 이전 항에서 일정한 수(공비)를 곱해서 얻어지는 수열이다

• 2, 4, 8, 16, ... (공비 2)
• 1, 1/2, 1/4, 1/8, ... (공비 1/2)

수열의 시작 항(초항)을 $a$라고 하고 공비를 $r$이라고 해보자

그러면 다음을 구할 수 있다

• 등비수열의 일반항 : $a_n = a * r^{n-1}$
• 등비수열의 합
  • 공비가 1일 때에는 모든 수열의 수가 같으니까 a를 n번 곱한 것이 된다
    • $S_n = a * n$
  • 공비가 1이 아닐 때
    • $S_n = a * (1-r^n)/(1-r)$

문제

백준 15712번

문제

풀이

단순하게 이 문제를 재귀를 이용해 큰 수의 거듭제곱을 구하는 방법을 사용해서 공식에 대입해 풀려고 했는데 문제가 있었다

등비수열의 합 공식이 나눗셈이 필요한 형태인데 우리가 흔히 아는 mod 연산은 사용할 수 없었다

그리고 풀이 과정 중에 소수라는 조건이 없기에 페르마의 소정리를 적용할 수 없다고 찾았는데 나중에 이건 따로 공부해보자

그래서 풀이 방식을 어떻게 가져가냐면 n이 짝수일 때와 홀수일 때로 구분할 수 있다

• n이 짝수
  • 짝수일 때 등비수열의 합은 n의 1/2까지의 등비수열의 합에서 (1 + $r^{n/2}$)를 곱해준 값이다
  • $S_n = S_{n/2}·(1+r^{n/2})$
• n이 홀수
  • $S_n = S_{n/2}·(1+r^{n/2}) + r^{n-1}$

코드

#include <bits/stdc++.h>

using namespace std;

long long a, r, n, mod;
long long answer;

void Input() 
{
	cin >> a >> r >> n >> mod;
}

long long POW(long long A, long long B)
{
	if (B == 0)
	{
		return 1;
	}

	long long half = POW(A, B / 2);
	long long num = (half * half) % mod;

	if (B % 2)
	{
		num = (num * A) % mod;
	}


	return num % mod;
}

long long Func(long long r, long long n)
{
	if (n == 1) return 1;

	if (n % 2)
	{
		return ((Func(r, n / 2) * (1 + POW(r, n / 2))) % mod + POW(r, n - 1)) % mod;
	}
	else
	{
		return (Func(r, n / 2) * (1 + POW(r, n / 2))) % mod;
	}
}

void Solve()
{
	cout << (a * Func(r, n) % mod);
}

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	Input();
	Solve();

	return 0;
}