피보나치 수열

https://www.acmicpc.net/blog/view/28

피보나치 수를 구하는 여러가지 방법

 

 

 

https://www.acmicpc.net/problem/11444

11444번: 피보나치 수 6

주기의 길이가 P 이면, N번째 피보나치 수를 M으로 나눈 나머지는 N%P번째 피보나치 수를 M을 나눈 나머지와 같습니다.

M = 10k 일 때, k > 2 라면, 주기는 항상 15 × 10k-1 입니다. 이 사실을 모른다고 해도, 주기를 구하는 코드를 이용해서 문제를 풀 수 있습니다.

이 문제에서 M = 106 이기 때문에, 주기는 15 × 105 = 1500000가 되겠네요.

 

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#include <ctime>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define LL long long
#define ULL unsigned long long
#define INF 987654321
#define MOD 1000000
#define endl '\n'

using namespace std;

ULL N;
const int P = MOD / 10 * 15;
int fibo[P] = { 0, 1 };

void solution() {
	cin >> N;
	for (int i = 2; i < P; i++) {
		fibo[i] = fibo[i - 1] + fibo[i - 2];
		fibo[i] %= MOD;
	}
	cout << fibo[N % P] << endl;
}

int main() {
	fastio;
	solution();

	return 0;
}

 

 

https://www.acmicpc.net/problem/11444

11444번: 피보나치 수 6

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#include <ctime>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define LL long long
#define ULL unsigned long long
#define INF 987654321
#define MOD 1000000007
#define endl '\n'

using namespace std;

LL N;
map<LL, LL> m;

LL solution(LL N) {
	if (N <= 0) return 0;
	if (N == 1 || N == 2) return 1;
	LL& ret = m[N];
	if (ret > 0) return ret;

	if (N % 2 != 0) {
		LL index = (N + 1) / 2;
		LL ps1 = solution(index);
		LL ps2 = solution(index - 1);
		m[N] = ps1 * ps1 + ps2 * ps2;
	}
	else {
		LL index = N / 2;
		LL ps1 = solution(index);
		LL ps2 = solution(index - 1);
		m[N] = ps1 * (ps1 + 2 * ps2);
	}
	m[N] %= MOD;
	return m[N];
}

void input() {
	cin >> N;
	cout << solution(N) << endl;
}

int main() {
	fastio;
	input();

	return 0;
}