Projet Euler : 304

Aujourd'hui n'a pas été une journée productive. J'ai pu finir de compiler quelques dépendances pour construire un noyau… mais à part ça, je n'en ai pas fait trop.
Quoi qu'il en soit, ce problème n'est pas difficile. Je pense que ça devrait être quelque chose comme 15%.
J'ai fait une petite astuce, car j'ai calculé les nombres premiers séparément et les ai enregistrés dans un fichier texte. Mathematica a été vraiment utile et rapide pour calculer les nombres premiers dans une plage. Quelque chose d'aussi simple que :

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

Maintenant, le problème nécessite de calculer les valeurs de Fibonacci de ces nombres premiers et de les additionner.
Vous savez, les nombres de Fibonacci ont une croissance exponentielle, donc on s'attend à ce qu'ils aient de grands nombres ici. Heureusement, le problème ne nécessite que de le calculer sous le mod 1234567891011.
Nous avons besoin d'une méthode logarithmique pour calculer rapidement les nombres de fibonacci. Je vais expliquer comment les matrices peuvent aider ici.

Jetez un œil à l'équation suivante :

C'est la définition matricielle d'un nombre de Fibonacci. Maintenant, je vais l'étendre davantage:

Cela a encore du sens, n'est-ce pas ? Maintenant, jetez un oeil à ceci:

Probablement, vous savez comment faire une exponentiation efficace. Il s'agit d'une méthode algorithmique bien connue appelée diviser pour régner, et dans ce cas, il s'agit d'une exponentiation binaire. Je ne l'expliquerai que pour les nombres entiers, mais cela s'applique également aux matrices.

Supposons que vous vouliez calculer : 2¹⁰

L'algorithme effectue les opérations suivantes :

2¹⁰ = 2⁵ * 2⁵

2⁵ = 2² * 2² * 2

2² = 2*2

et c'est tout. Comme vous pouvez le voir, à chaque étape, nous divisons l'exposant par deux, si l'exposant est pair, nous aurons deux puissances égales, si l'exposant est impair, nous pouvons simplement soustraire 1 de l'exposant et procéder comme s'il était pair.

Puisqu'à chaque étape nous divisons l'exposant par deux, le nombre d'opérations attendu est log2(n). Cet algorithme est donc logarithmique.

Revenons au problème. Nous avons un moyen de calculer de grands nombres de Fibonacci sous un mod en temps logarithmique. Ainsi, même si les chiffres sont énormes, nous pouvons les calculer rapidement.

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