भारी संख्या के रिटायरमेंट रकम कैसे पाएं? [डुप्लिकेट]
मैं एक CSES समस्या हल कर रहा हूँ जिसमें मुझे पहले 'n' फाइबोनैचि संख्याओं का योग ज्ञात करना है। कोड:
#pragma GCC optimize("Ofast")
#include <iostream>
using namespace std;
int main()
{
unsigned long long int n;
scanf("%llu", &n);
unsigned long long int seq[n];
seq[0] = 0;
seq[1] = 1;
unsigned long long int mod = 1000000000 + 7;
for (unsigned long long int i = 2; i < n + 1; i++) {
seq[i] = (seq[i - 1] + seq[i - 2]) % mod;
}
cout << seq[n];
}
समस्या निर्दिष्ट करती है कि n का मान 10 ^ 18 तक हो सकता है और इसलिए मैंने unsigned long long int
n को इनिशियलाइज़ करने के लिए उपयोग किया है। समस्या मॉडुलो 7 का उत्तर देने का भी निर्देश देती है। कोड 4 अंको तक के मानों के लिए ठीक काम कर रहा है, लेकिन तब टूटता है जब n का मान 10 ^ 18 की ऊपरी छत तक बढ़ जाता है। यह एक (0xC00000FD)
त्रुटि देता है और कुछ भी वापस नहीं करता है। कृपया मुझे यहाँ समस्या को समझने और इससे निपटने के तरीके में मदद करें। किसी अन्य सुझाव की भी सराहना की जाएगी।
जवाब
इस समस्या में
एफ [i] -> मैं वें फाइबोनैचि संख्या। MOD = 1e9 + 7. n <1e18
F [n]% MOD =?
F [n] = F [n-1] + F [n-2] यदि आप लूप से यह गणना करते हैं कि आपको टीएल मिलता है
इस तरह से आप इस समाधान का अनुकूलन कर सकते हैं
अब आप पुनरावर्तन के साथ F [n] की गणना करते हैं
एफ [2 * एन] = - एफ [एन] * एफ [एन] + 2 * एफ [एन] * एफ [एन + 1]
एफ [2 * एन + 1] = एफ [एन] * एफ [एन] + एफ [एन + 1] * एफ [एन + 1]
यहाँ मेरा समाधान है
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MOD = 1e9+7;
void fib(ll n ,ll &a , ll &b){
if(n == 0){
a = 0;
b = 1;
return;
}
ll x, y;
if(n%2==1){
fib(n-1 ,x,y);
a = y;
b = (x+y)%MOD;
return;
}
fib(n/2 , x , y);
a = (x*(2*y +MOD -x)%MOD)%MOD;
b = ((x*x)%MOD+(y*y)%MOD)%MOD;
return;
}
int main(){
ll N , a, b;
cin >> N;
fib(N , a, b);
cout << a;
}
मॉड्यूलर जोड़ते समय, आपको अपने मॉड को आपके द्वारा जोड़े जा रहे प्रत्येक मान पर लागू करने की आवश्यकता होती है।
उदाहरण के लिए, (a + b)% c = (a% c + b% c)% c।
आपके कोड में इसका मतलब है:
seq[i] = (seq[i - 1] % mod + seq[i - 2] % mod) % mod;
अन्यथा, के अलावा seq[i - 1]
और seq[i - 2]
एक अतिप्रवाह में परिणाम होगा।
मॉड्यूलर अंकगणितीय बारे में अधिक पढ़ें यहाँ ।
मुझे लगता है कि इस कोड के साथ समस्या यह है कि आप seq[n]
आकार की एक सरणी बना रहे हैं n
, जिससे SEGFAULT
लिनक्स STATUS_STACK_OVERFLOW (0xc00000fd)
पर और विंडोज पर बड़ी संख्या में हो सकता है, जो स्टैक थकावट को संदर्भित करता है।
नीचे मैं आपके एल्गोरिथ्म का एक उन्नत संस्करण देता हूं, जो एक निश्चित मेमोरी साइज का उपयोग करता है, और मोड्यूलो जोड़ के लिए, मैं sum_by_modulo
फ़ंक्शन का उपयोग करता हूं , (a + b) % m
ऑपरेशन में अतिप्रवाह से बचने के लिए , जिसका सिद्धांत यहां वर्णित है ।
#pragma GCC optimize("Ofast")
#include <iostream>
typedef unsigned long long int ullong;
ullong sum_by_modulo(ullong a, ullong b, ullong m){
ullong sum;
a %= m;
b %= m;
ullong c = m - a;
if (b==c)
sum = 0;
if (b<c)
sum = a + b;
if (b > c)
sum = b-c;
return sum;
}
int main()
{
ullong n;
ullong t1 = 0, t2 = 1, nextTerm = 0;
ullong modulo = 1000000000 + 7;
std::cout << "Enter the number of term: ";
std::cin >> n;
for (ullong i = 1; i <= n; ++i)
{
if(i == 1)
continue;
if(i == 2)
continue;
nextTerm = sum_by_modulo(t1, t2, modulo);
t1 = t2;
t2 = nextTerm;
}
std::cout << nextTerm << " ";
return 0;
}