फ़िबोनाची अनुक्रम का n-वाँ पद (mod m) की गणना
फ़िबोनाची अनुक्रम इस तरह परिभाषित होता है कि हर अगला पद पिछले दो पदों को जोड़कर बनता है, जबकि पहले दो पद 0 और 1 हैं:
आपको संख्या
n दी गई है, और इसका n-वाँ फ़िबोनाची मान m से मॉड्यूलो करने पर प्राप्त करना है।क्योंकि हमें केवल का परिणाम चाहिए,
n का मान बहुत बड़ा हो सकता है।इनपुट
इनपुट की एकमात्र पंक्ति में दो पूर्णांक
n (0 ≤ n ≤ ) और m (1 ≤ m ≤ 50) दिए होते हैं।आउटपुट
कार्यक्रम को का परिणाम प्रिंट करना चाहिए।
उदाहरण
Input | Output |
0 5 | 0 |
1 5 | 1 |
6 5 | 3 |
व्याख्या
- fib(0) = 0 ⇒ 0 mod 5 = 0
- fib(1) = 1 ⇒ 1 mod 5 = 1
- fib(6) = 8 ⇒ 8 mod 5 = 3
Hint 1
क्योंकि हम फ़िबोनाची संख्याओं की गणना
m से मॉड्यूलो लेकर कर रहे हैं, और अगली संख्या हमेशा पिछली दो पर निर्भर करती है, किसी बिंदु पर ये संख्याएँ दोहराने लगती हैं। आप m से मॉड्यूलो की कई मानों को प्रिंट करके देख सकते हैं और यह पैटर्न नोट कर सकते हैं कि वे कब से दोहराना शुरू करते हैं।Hint 2
जैसा कि संख्याएँ एक बिंदु पर दोहराना शुरू कर देती हैं, आप सारे मान एक-एक करके निकालने के बजाय सीधे
n-वाँ फ़िबोनाची नंबर ज्ञात कर सकते हैं।Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB