Wie findet man Fibonacci-Summen mit großen Zahlen? [Duplikat]

Dec 21 2020

Ich löse ein CSES-Problem, bei dem ich die Summe der ersten 'n' Fibonacci-Zahlen finden muss. Der 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];
}

Das Problem gibt an, dass der Wert von n bis zu 10 ^ 18 betragen kann, und deshalb habe ich unsigned long long int n initialisiert. Das Problem weist auch an, dem Modulo 7 eine Antwort zu geben. Der Code funktioniert einwandfrei für Werte von n bis zu 4 Stellen, bricht jedoch ab, wenn der Wert von n auf die obere Obergrenze von 10 ^ 18 ansteigt. Er gibt einen (0xC00000FD)Fehler aus und gibt nichts zurück. Bitte helfen Sie mir, das Problem hier zu verstehen und wie ich damit umgehen soll. Alle anderen Vorschläge wäre auch dankbar.

Antworten

1 JamshidKodirov Dec 21 2020 at 15:50

In diesem Problem

F [i] -> i-te Fibonacci-Zahl. MOD = 1e9 + 7. n <1e18

F [n]% MOD =?

F [n] = F [n-1] + F [n-2] Wenn Sie dies mit einer Schleife berechnen, erhalten Sie TL

Auf diese Weise können Sie diese Lösung optimieren

Jetzt berechnen Sie F [n] mit Rekursion

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]

Hier ist meine Lösung

#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;
}
2 a.Li Dec 21 2020 at 15:04

Wenn Sie modular hinzufügen, müssen Sie Ihren Mod auf jeden Wert anwenden, den Sie hinzufügen.

Zum Beispiel ist (a + b)% c = (a% c + b% c)% c.

Das heißt in Ihrem Code:

seq[i] = (seq[i - 1] % mod + seq[i - 2] % mod) % mod;

Andernfalls führt das Hinzufügen von seq[i - 1]und seq[i - 2]zu einem Überlauf.

Lesen Sie mehr über modulare Arithmetik hier .

alex_noname Dec 21 2020 at 15:50

Ich denke, das Problem mit diesem Code ist, dass Sie ein Array seq[n]von Größe erstellen n, was SEGFAULTunter Linux und STATUS_STACK_OVERFLOW (0xc00000fd)Windows zu einer großen Anzahl führen kann, was auf die Erschöpfung des Stacks hinweist.

Im Folgenden gebe ich eine verbesserte Version Ihres Algorithmus an, der eine feste Speichergröße verwendet, und für die Modulo-Addition verwende ich die sum_by_moduloFunktion, um einen Überlauf im (a + b) % mBetrieb zu vermeiden , dessen Prinzip hier beschrieben wird .

#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;
}