Euler Projesi: 304

Bugün verimli bir gün olmadı. Bir çekirdek oluşturmak için bazı bağımlılıkları derlemeyi bitirebildim… ama bunun dışında çok fazla bir şey yapmadım.
Her neyse, bu problem zor değil. Bence %15 gibi bir şey olmalı.
Biraz hile yaptım çünkü asal sayıları ayrı ayrı hesapladım ve bir metin dosyasına kaydettim. Mathematica, bir aralıktaki asal sayıları hesaplamak için gerçekten yardımcı ve hızlıydı. Şu kadar basit bir şey:

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

Şimdi problem bu asal sayıların Fibonacci değerlerinin hesaplanmasını ve toplanmasını gerektiriyor.
Biliyorsunuz Fibonacci sayıları üstel bir büyüme sergiliyor dolayısıyla burada büyük sayıların olması bekleniyor. Neyse ki, sorun sadece mod 1234567891011 altında hesaplamayı gerektiriyor.
Fibonacci sayılarını hızlı bir şekilde hesaplamak için logaritmik bir yönteme ihtiyacımız var. Burada matrislerin nasıl yardımcı olabileceğini açıklayacağım.

Bir sonraki denkleme bir göz atın:

Bir fibonacci sayısının matris tanımıdır. Şimdi daha da genişleteceğim:

Hala mantıklı, değil mi? Şimdi, şuna bir göz atın:

Muhtemelen, üs almanın verimli bir şekilde nasıl yapıldığını biliyorsunuzdur. Böl ve fethet adı verilen iyi bilinen bir algoritmik yöntemdir ve bu durumda ikili üs almadır. Bunu sadece tamsayılar için açıklayacağım ama bu matrisler için de geçerli.

Diyelim ki, şunu hesaplamak istiyorsunuz: 2¹⁰

Algoritma aşağıdakileri yapar:

2¹⁰ = 2⁵ * 2⁵

2⁵ = 2² * 2² * 2

2² = 2*2

ve hepsi bu Gördüğünüz gibi, her adımda üssü ikiye bölüyoruz, eğer üs çift ise, iki eşit kuvvetimiz olacak, üs tekse, üssün 1'ini çıkarabiliriz ve sanki çiftmiş gibi devam edebiliriz.

Her adımda üssü ikiye böldüğümüz için, beklenen işlem sayısı log2(n)'dir. Yani, bu algoritma logaritmiktir.

Soruna geri dön. Logaritmik zamanda bir mod altında büyük fibonacci sayılarını hesaplamanın bir yolunu bulduk. Böylece, rakamlar çok büyük olsa bile, bunları hızlı bir şekilde hesaplayabiliriz.

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