Module: دالة أويلر ومشكلات أخرى في نظرية الأعداد


Problem

9/9

** نموذج أرقام فيبوناتشي (C ++)

Theory Click to read/hide

أرقام مودولو فيبوناتشي للعثور على رقم فيبوناتشي بكفاءة ، نستخدم ضرب المصفوفة ، مزيد من التفاصيل هنا .
نبسب ؛
مع العلم أن نبسب؛
\ (F_ {n + m} = F_m F_ {n + 1} + F_ {m-1} F_n \) ، & nbsp؛ اكتب علاقة التكرار لمنتج المصفوفة:
& الثور؛ إذا \ (m = n \) ثم \ (F_ {2n} = F_n F_ {n + 1} + F_ { n-1} F_n \) ؛
& الثور؛ إذا \ (m = n + 1 \) ثم \ (F_ {2n + 1} = F_ {n + 1} F_ {n + 1} + F_n F_n \) .
& nbsp؛

Problem

كما تعلم ، يتم تعريف تسلسل فيبوناتشي على النحو التالي:
\ (F (0) = 0، \ F (1) = 1، \ F (n) = F (n - 1) + F (n - 2) \ ) ، لجميع \ (n & gt؛ 1 \) .
تمت تسميته على اسم عالم الرياضيات الإيطالي ليوناردو فيبوناتشي ، المعروف أيضًا باسم ليوناردو بيزا.
& nbsp؛
إدخال
تحتوي السلسلة على عدد صحيح n ( \ (1 & lt؛ = n & lt؛ = 10 ^ {18} \) ).
& nbsp؛
الإخراج
طباعة قيمة F (n) ، & nbsp ؛ modulo المحسوب \ (10 ​​^ 8 \) .

الصق مقتطف الشفرة المفقود في البرنامج.

أمثلة <الجسم>
# إدخال الإخراج
1 30 832040

نبسب ؛