Projekt Euler: 304

Heute war kein produktiver Tag. Ich konnte einige Abhängigkeiten fertig kompilieren, um einen Kernel zu bauen … aber ansonsten habe ich nicht allzu viel getan.
Wie auch immer, dieses Problem ist nicht schwierig. Ich denke, es sollten ungefähr 15% sein.
Ich habe einen kleinen Trick gemacht, weil ich die Primzahlen separat berechnet und in einer Textdatei gespeichert habe. Mathematica war wirklich hilfreich und schnell, um Primzahlen in einem Bereich zu berechnen. Etwas so Einfaches wie:

Prime[Range[PrimePi[10^14]+1, PrimePi[10^14]+10^5]]

Das Problem besteht nun darin, die Fibonacci-Werte dieser Primzahlen zu berechnen und sie zu addieren.
Wissen Sie, Fibonacci-Zahlen haben ein exponentielles Wachstum, also wird hier mit großen Zahlen gerechnet. Glücklicherweise muss das Problem nur unter Mod 1234567891011 berechnet werden.
Wir brauchen eine logarithmische Methode, um die Fibonacci-Zahlen schnell zu berechnen. Ich werde erklären, wie Matrizen hier helfen können.

Schauen Sie sich die nächste Gleichung an:

Es ist die Matrixdefinition einer Fibonacci-Zahl. Jetzt erweitere ich es weiter:

Es macht immer noch Sinn, oder? Nun schau dir das an:

Wahrscheinlich wissen Sie, wie man effizient potenziert. Es ist eine bekannte algorithmische Methode namens Teile und herrsche, und in diesem Fall ist es die binäre Potenzierung. Ich werde es nur für ganze Zahlen erklären, aber es gilt auch für Matrizen.

Angenommen, Sie möchten berechnen: 2¹⁰

Der Algorithmus macht folgendes:

2¹⁰ = 2⁵ * 2⁵

2⁵ = 2² * 2² * 2

2² = 2*2

und es ist alles. Wie Sie sehen können, teilen wir den Exponenten in jedem Schritt durch zwei, wenn der Exponent gerade ist, haben wir zwei gleiche Potenzen, wenn der Exponent ungerade ist, können wir einfach 1 des Exponenten subtrahieren und so weitermachen, als ob er gerade wäre.

Da wir in jedem Schritt den Exponenten durch zwei dividieren, ist die erwartete Anzahl von Operationen log2(n). Dieser Algorithmus ist also logarithmisch.

Zurück zum Problem. Wir haben eine Möglichkeit, große Fibonacci-Zahlen unter einem Mod in logarithmischer Zeit zu berechnen. Also, selbst wenn die Zahlen riesig sind, können wir sie schnell berechnen.

#include <bits/stdc++.h>
using namespace std;
using ll = __int128;

#define MOD 1234567891011

typedef vector<vector<ll> > Matrix;
Matrix ones(int n) {
    Matrix r(n,vector<ll>(n));
    for(int i=0; i<n; i++) r[i][i]=1;
    return r;
}
Matrix operator*(Matrix &a, Matrix &b){
    int n=a.size(),m=b[0].size(),z=a[0].size();
    Matrix r(n,vector<ll>(m));
    for(int i=0; i<n; i++)for(int j=0; j<m; j++)for(int k=0; k<z; k++)
        r[i][j]+=a[i][k]*b[k][j],r[i][j]%=MOD;
    return r;
}
Matrix be(Matrix b, ll e) {
    Matrix r=ones(b.size());
    while(e){if(e&1LL)r=r*b;b=b*b;e>>=1;}
    return r;
}    

ll fib(ll n){
    Matrix fibo(2, vector <ll>(2));
    fibo[0] = {1, 1};
    fibo[1] = {1, 0};
    Matrix F = be(fibo, n);
    return F[1][0]%MOD;
}

int main(){
    unsigned long long p;
    ll ans = 0;
    while(cin >> p){
        ans += fib(p);
        ans %= MOD;
    }
    unsigned long long out = ans;
    cout << out << '\n';
    return 0;
}