거대한 숫자의 피보나치 합계를 찾는 방법은 무엇입니까? [복제]
저는 처음 'n'피보나치 수의 합을 찾아야하는 CSES 문제를 해결하고 있습니다. 코드:
#pragma GCC optimize("Ofast")
#include <iostream>
using namespace std;
int main()
{
unsigned long long int n;
scanf("%llu", &n);
unsigned long long int seq[n];
seq[0] = 0;
seq[1] = 1;
unsigned long long int mod = 1000000000 + 7;
for (unsigned long long int i = 2; i < n + 1; i++) {
seq[i] = (seq[i - 1] + seq[i - 2]) % mod;
}
cout << seq[n];
}
문제는 n의 값이 10 ^ 18까지 될 수 있으므로 unsigned long long int
n을 초기화 하는 데 사용 했습니다. 문제는 또한 모듈로 7 답변을 제공하도록 지시합니다. 이 코드는 4 자리까지의 n 값에 대해 잘 작동하지만 n 값이 10 ^ 18의 상한선까지 올라가면 중단됩니다. (0xC00000FD)
오류가 발생하고 아무것도 반환하지 않습니다. 여기에있는 문제와 처리 방법을 이해하도록 도와주세요. 다른 제안도 감사하겠습니다.
답변
이 문제에서
F [i]-> i 번째 피보나치 수. MOD = 1e9 + 7. n <1e18
F [n] % MOD =?
F [n] = F [n-1] + F [n-2] 루프로 이것을 계산하면 TL을 얻습니다.
이 솔루션을 최적화 할 수있는 방법입니다.
이제 재귀로 F [n]을 계산합니다.
F [2 * n] =-F [n] * F [n] + 2 * F [n] * F [n + 1]
F [2 * n + 1] = F [n] * F [n] + F [n + 1] * F [n + 1]
여기 내 해결책이 있습니다
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MOD = 1e9+7;
void fib(ll n ,ll &a , ll &b){
if(n == 0){
a = 0;
b = 1;
return;
}
ll x, y;
if(n%2==1){
fib(n-1 ,x,y);
a = y;
b = (x+y)%MOD;
return;
}
fib(n/2 , x , y);
a = (x*(2*y +MOD -x)%MOD)%MOD;
b = ((x*x)%MOD+(y*y)%MOD)%MOD;
return;
}
int main(){
ll N , a, b;
cin >> N;
fib(N , a, b);
cout << a;
}
모듈 식 추가를 수행 할 때 추가하는 각 값에 모드를 적용해야합니다.
예를 들어, (a + b) % c = (a % c + b % c) % c.
이는 코드에서 다음을 의미합니다.
seq[i] = (seq[i - 1] % mod + seq[i - 2] % mod) % mod;
그렇지 않은 경우의 추가 seq[i - 1]
및 seq[i - 2]
오버 플로우가 발생합니다.
여기에서 모듈 식 산술에 대해 자세히 읽어보십시오 .
이 코드의 문제는 당신이 배열을 만드는 것을 생각 seq[n]
크기의 n
A를 초래할 수, SEGFAULT
리눅스와 STATUS_STACK_OVERFLOW (0xc00000fd)
피로를 쌓아 의미 많은 수의 Windows에 있습니다.
아래에서는 고정 메모리 크기를 사용하는 알고리즘의 개선 된 버전을 제공하고 모듈로 추가의 경우 작동 중 sum_by_modulo
오버플로를 방지 하기 위해 함수를 사용합니다 (a + b) % m
. 그 원리는 여기에 설명되어 있습니다 .
#pragma GCC optimize("Ofast")
#include <iostream>
typedef unsigned long long int ullong;
ullong sum_by_modulo(ullong a, ullong b, ullong m){
ullong sum;
a %= m;
b %= m;
ullong c = m - a;
if (b==c)
sum = 0;
if (b<c)
sum = a + b;
if (b > c)
sum = b-c;
return sum;
}
int main()
{
ullong n;
ullong t1 = 0, t2 = 1, nextTerm = 0;
ullong modulo = 1000000000 + 7;
std::cout << "Enter the number of term: ";
std::cin >> n;
for (ullong i = 1; i <= n; ++i)
{
if(i == 1)
continue;
if(i == 2)
continue;
nextTerm = sum_by_modulo(t1, t2, modulo);
t1 = t2;
t2 = nextTerm;
}
std::cout << nextTerm << " ";
return 0;
}