Comment trouver des sommes de fibonacci de nombres énormes? [dupliquer]
Je résous un problème du CSES dans lequel je dois trouver la somme des premiers 'n' nombres de Fibonacci. Le code:
#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];
}
Le problème spécifie que la valeur de n peut atteindre 10 ^ 18 et que j'ai donc utilisé unsigned long long int
pour initialiser n. Le problème demande également de donner la réponse modulo 7. Le code fonctionne bien pour les valeurs de n jusqu'à 4 chiffres, mais se rompt lorsque la valeur de n atteint le plafond supérieur de 10 ^ 18.Il donne une (0xC00000FD)
erreur et ne renvoie rien. S'il vous plaît, aidez-moi à comprendre le problème ici et comment y faire face. Toute autre suggestion serait également appréciée.
Réponses
Dans ce problème
F [i] -> i ème numéro de Fibonacci. MOD = 1e9 + 7. n <1e18
F [n]% MOD =?
F [n] = F [n-1] + F [n-2] si vous calculez cela avec une boucle, vous obtenez TL
c'est ainsi que vous pouvez optimiser cette solution
maintenant vous calculez F [n] avec récursion
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]
voici ma solution
#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;
}
Lors de l'ajout modulaire, vous devez appliquer votre mod à chaque valeur que vous ajoutez.
Par exemple, (a + b)% c = (a% c + b% c)% c.
Cela signifie dans votre code:
seq[i] = (seq[i - 1] % mod + seq[i - 2] % mod) % mod;
Sinon, l'ajout de seq[i - 1]
et seq[i - 2]
entraînera un débordement.
En savoir plus sur l'arithmétique modulaire ici .
Je pense que le problème avec ce code est que vous créez un tableau seq[n]
de taille n
, ce qui peut conduire à un SEGFAULT
sur Linux et STATUS_STACK_OVERFLOW (0xc00000fd)
sur Windows pour de grands nombres, qui fait référence à l'épuisement de la pile.
Ci-dessous, je donne une version améliorée de votre algorithme, qui utilise une taille de mémoire fixe, et pour l'ajout de modulo, j'utilise la sum_by_modulo
fonction, pour éviter les débordements en (a + b) % m
fonctionnement, dont le principe est décrit ici .
#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;
}