글 읽기 - 왜 계속 틀렸습니다가 나올까요?

kimdongyul51 4년 전 2

뭔가 %15746에서 틀린 것 같은데 저는 못 찾겠어요.

#include <stdio.h>

long long fib[1000001];

int main()
{
	int n, i;
	
	scanf("%d", &n);
	
	fib[1] = 1;
	fib[2] = 2;
	fib[3] = 3;
	
	for(i=4;i<=n;i++)
	{
		fib[i] = fib[i-1] + fib[i-2];
	}
	
	printf("%lld\n",fib[n] % 15746);
}

scvhero 4년 전 2

피보나치 수열은 100번째 수가 되기도 전에 64bit 정수형의 범위를 초과합니다

djm03178 4년 전 2

백만 번째 피보나치 수는 long long이 표현할 수 있는 범위를 압도적으로 벗어납니다. 이미 오버플로우가 발생한 뒤에 나머지 연산을 하면 늦고, 연산 과정에서 계속 나머지를 취해줘야 합니다.

kimdongyul51 4년 전 1

그럼 long long 보다 큰 표현 방법이 있나요?

kimdongyul51 4년 전 1

감사합니다. 덕분에 풀었습니다.

yeopgi 4년 전 0

감사합니다 저도 엄청 궁금했는데 참고했습니다 !!!

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

문제

문제

출처

ICPC

왜 계속 틀렸습니다가 나올까요?

kimdongyul51 4년 전 2

scvhero 4년 전 2

djm03178 4년 전 2

kimdongyul51 4년 전 1

kimdongyul51 4년 전 1

yeopgi 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말