Projekt Euler: 304

Dzisiejszy dzień nie był produktywny. Udało mi się dokończyć kompilację niektórych zależności w celu zbudowania jądra… ale poza tym nie zrobiłem zbyt wiele.
W każdym razie ten problem nie jest trudny. Myślę, że powinno to być około 15%.
Zrobiłem mały trik, bo osobno policzyłem liczby pierwsze i zapisałem je w pliku tekstowym. Mathematica była naprawdę pomocna i szybka w obliczaniu liczb pierwszych w zakresie. Coś tak prostego jak:

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

Teraz problem wymaga obliczenia wartości Fibonacciego tych liczb pierwszych i zsumowania ich.
Wiesz, liczby Fibonacciego rosną wykładniczo, więc oczekuje się, że tutaj będą duże liczby. Na szczęście problem wymaga tylko obliczenia pod mod 1234567891011.
Potrzebujemy metody logarytmicznej, aby szybko obliczyć liczby Fibonacciego. Wyjaśnię, w jaki sposób matryce mogą tutaj pomóc.

Spójrz na następne równanie:

To macierzowa definicja liczby Fibonacciego. Teraz rozszerzę to bardziej:

To nadal ma sens, prawda? A teraz spójrz na to:

Prawdopodobnie wiesz, jak skutecznie potęgować. Jest to dobrze znana metoda algorytmiczna zwana dziel i zwyciężaj, aw tym przypadku jest to potęgowanie binarne. Wyjaśnię to tylko dla liczb całkowitych, ale dotyczy to również macierzy.

Załóżmy, że chcesz obliczyć: 2¹⁰

Algorytm wykonuje następujące czynności:

2¹⁰ = 2⁵ * 2⁵

2⁵ = 2² * 2² * 2

2² = 2*2

i to wszystko. Jak widać, w każdym kroku dzielimy wykładnik przez dwa, jeśli wykładnik jest parzysty, będziemy mieli dwie równe potęgi, jeśli wykładnik jest nieparzysty, możemy po prostu odjąć 1 od wykładnika i postępować tak, jakby był parzysty.

Ponieważ w każdym kroku dzielimy wykładnik przez dwa, oczekiwana liczba operacji to log2(n). Zatem ten algorytm jest logarytmiczny.

Wróćmy do problemu. Mamy sposób na obliczanie dużych liczb Fibonacciego pod modą w czasie logarytmicznym. Tak więc, nawet jeśli liczby są ogromne, możemy je szybko obliczyć.

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