글 읽기 - 질문이요

jyj041053 5년 전 0

피보나치 성질을 이용해서 합구하는 문제를 풀었는데 특정수의 끝에 아홉자리가 000000000이라 d[n]에 0이 들어가면서 오답이 나오네요

어떻게 처리하면 좋을까요ㅠ

#include <iostream>
#include <map>

using namespace std;

map<long long, long long> d;
const long long mod = 1000000000LL;

long long fibo(long long n) {
	if (n == 0)
		return 0;
	else if (n == 1 || n == 2)
		return 1;
	else  if (d.count(n) > 0)
		return d[n];
	else {
		if (n % 2 == 1) {
			long long m = (n + 1) / 2;
			long long t1 = fibo(m);
			long long t2 = fibo(m - 1);
			d[n] = t1*t1 + t2*t2;
			d[n] %= mod;
			return d[n];
		}
		else {
			long long m = n / 2;
			long long t1 = fibo(m);
			long long t2 = fibo(m - 1);
			d[n] = (2LL * t2 + t1)*t1;
			d[n] %= mod;
			return d[n];
		}
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	long long a, b;
	cin >> a >> b;
	long long num1 = fibo(b + 2);
	long long num2 = fibo(a + 1);
	cout << (num1 - num2) % mod << '\n';
	return 0;
}

startlink 5년 전 0

과연 그게 틀린 이유일까요??

startlink 5년 전 0

num1 < num2 가 되면 정답이 잘 나올까요

jyj041053 5년 전 0

그 부분을 고쳐봐도 틀렸습니다라고 나오네요ㅠ

startlink 5년 전 0

(num1 - num2 + mod) % mod

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

질문이요

jyj041053 5년 전 0

startlink 5년 전 0

startlink 5년 전 0

jyj041053 5년 전 0

startlink 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말