प्रोजेक्ट यूलर: 304

आज का दिन उत्पादक नहीं रहा। मैं कर्नेल बनाने के लिए कुछ निर्भरताओं को संकलित करने में सक्षम था ... लेकिन इसके अलावा, मैंने बहुत कुछ नहीं किया।
वैसे यह समस्या कोई कठिन नहीं है। मुझे लगता है, यह 15% जैसा कुछ होना चाहिए।
मैंने थोड़ी सी चाल चली, क्योंकि मैंने अभाज्य संख्याओं की अलग से गणना की और उन्हें एक टेक्स्ट फ़ाइल में सहेजा। एक श्रेणी में अभाज्य संख्याओं की गणना करने के लिए गणित वास्तव में सहायक और तेज़ था। कुछ इतना आसान:

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

अब, समस्या के लिए इन अभाज्य संख्याओं के फाइबोनैचि मानों की गणना करने और उन्हें जोड़ने की आवश्यकता है।
आप जानते हैं, फाइबोनैचि संख्या में घातीय वृद्धि होती है, इसलिए यहां बड़ी संख्या में होने की उम्मीद है। सौभाग्य से, समस्या को केवल मॉड 1234567891011 के तहत इसकी गणना करने की आवश्यकता है
। मैं समझाऊंगा कि मैट्रिसेस यहां कैसे मदद कर सकता है।

अगले समीकरण पर एक नज़र डालें:

यह फिबोनैकी संख्या की मैट्रिक्स परिभाषा है। अब, मैं इसे और अधिक विस्तारित करूँगा:

यह अभी भी समझ में आता है, है ना? अब, इसे देखें:

शायद, आप कुशलतापूर्वक घातांक करना जानते हैं। यह एक प्रसिद्ध एल्गोरिथम विधि है जिसे फूट डालो और जीतो कहा जाता है, और इस मामले में यह द्विआधारी घातांक है। मैं इसे केवल पूर्णांकों के लिए समझाऊंगा, लेकिन यह आव्यूहों के लिए भी लागू होता है।

मान लीजिए कि, आप गणना करना चाहते हैं: 2¹⁰

एल्गोरिथ्म निम्नलिखित करता है:

2¹⁰ = 2⁵ * 2⁵

2⁵ = 2² * 2² * 2

2² = 2*2

और यह सब है। जैसा कि आप देख सकते हैं, प्रत्येक चरण में हम घातांक को दो से विभाजित करते हैं, यदि घातांक सम है, तो हमारे पास दो समान शक्तियाँ होंगी, यदि घातांक विषम है तो हम केवल घातांक में से 1 घटा सकते हैं और आगे बढ़ सकते हैं जैसे कि वह सम था।

चूँकि प्रत्येक चरण में हम घातांक को दो से विभाजित कर रहे हैं, संक्रियाओं की अपेक्षित संख्या log2(n) है। तो, यह एल्गोरिदम लॉगरिदमिक है।

समस्या पर वापस। हमारे पास लॉगरिदमिक समय में एक मॉड के तहत बड़ी फाइबोनैचि संख्याओं की गणना करने का एक तरीका है। इसलिए, भले ही संख्याएँ बहुत बड़ी हों, हम उनकी शीघ्रता से गणना कर सकते हैं।

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