Proyek Euler: 304

Hari ini bukanlah hari yang produktif. Saya dapat menyelesaikan kompilasi beberapa dependensi untuk membangun sebuah kernel… tetapi selain itu, saya tidak melakukan terlalu banyak.
Lagi pula, masalah ini tidak sulit. Saya pikir, seharusnya sekitar 15%.
Saya melakukan sedikit trik, karena saya menghitung bilangan prima secara terpisah dan menyimpannya dalam file teks. Mathematica sangat membantu dan cepat menghitung bilangan prima dalam suatu rentang. Sesuatu yang sederhana seperti:

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

Sekarang, masalahnya membutuhkan perhitungan nilai Fibonacci dari bilangan prima ini dan menjumlahkannya.
Anda tahu, angka Fibonacci memiliki pertumbuhan eksponensial, jadi diharapkan angkanya besar di sini. Untungnya, masalahnya hanya perlu menghitungnya di bawah mod 1234567891011.
Kita memerlukan metode logaritma untuk menghitung angka fibonacci dengan cepat. Saya akan menjelaskan bagaimana matriks dapat membantu di sini.

Perhatikan persamaan selanjutnya:

Ini adalah definisi matriks dari angka fibonacci. Sekarang, saya akan memperluasnya lebih lanjut:

Masih masuk akal, bukan? Sekarang, lihat ini:

Mungkin, Anda tahu cara melakukan eksponensial secara efisien. Ini adalah metode algoritmik terkenal yang disebut membagi dan menaklukkan, dan dalam hal ini adalah eksponensial biner. Saya akan menjelaskannya hanya untuk bilangan bulat, tetapi berlaku juga untuk matriks.

Misalkan, Anda ingin menghitung: 2¹⁰

Algoritme melakukan hal berikut:

2¹⁰ = 2⁵ * 2⁵

2⁵ = 2² * 2² * 2

2² = 2*2

dan itu semua. Seperti yang Anda lihat, di setiap langkah kita membagi eksponen dengan dua, jika eksponennya genap, kita akan memiliki dua pangkat yang sama, jika eksponennya ganjil kita cukup mengurangkan 1 eksponen dan melanjutkan seolah-olah genap.

Karena dalam setiap langkah kita membagi eksponen dengan dua, jumlah operasi yang diharapkan adalah log2(n). Jadi, algoritma ini adalah logaritmik.

Kembali ke masalah. Kami memiliki cara untuk menghitung angka fibonacci besar di bawah mod dalam waktu logaritmik. Jadi, meski jumlahnya besar, kita bisa menghitungnya dengan cepat.

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