1樓：李俊南
大部分人會這麼寫
n = eval(input())
a = 0
b = 1
for i in range(n):
a,b = a+b, a
print(a%10007)
這樣寫沒有任何問題，但如果需要求第***項對10007取余時，我試了一下，三分鐘都沒有得出答案，電腦風扇狂轉。
有沒有更簡潔的辦法
答案是有的
我們這樣想，a%10007，是否等於(a+10007*n)%10007：(n為正整數)
答案是相等的
那(a+10008)%10007和(a+1)%10007取餘有區別嗎，當然也是沒有。
也就是說(a+b)%10007 = (a+b%10007)%10007
那麼我們的程式改寫成這樣
n = eval(input())
a = 0
b = 1
for i in range(n+1):
a,b = a+b, a%10007
print(b)
再試試第***項，三秒得出答案。
效率提公升了不少。
2樓：George2019
（1）為什麼 (a + b) mod m = (a mod m + b mod m) mod m?
這是同餘的性質。正是因為餘數可以提前取，不影響結果，才避免了大數的運算。證明的話把整數 a, b 都寫成帶餘除法形式：
a = p * m + r, b = q * m + s. 那麼有
a + b = (p + q) * m + r + s.
所以 a + b 和 r + s 相差整數倍的 m，它們是模 m 同餘的。故兩邊對 m 取余會相等，原式得證。可以提前取餘這件事還可以推廣到乘法和乘方（僅底數）。也就是有
(a * b) mod m = ((a mod m) * (b mod m)) mod m,
(a ^ b) mod m = ((a mod m) ^ b) mod m.
可以學習一下模 m 剩餘類環 Z(m) 的性質。
（2）如何將程式的時間複雜度由 O(n) 降低為 O(log2(n))？
即使知道了（1），只是迴避了大數，但項數 n 很大以後，求出 F[n] 需要一項一項遞推地算還是很慢。我們可以把遞推式 F[n] = F[n-1] + F[n-2] 寫成矩陣形式
這樣的話，求 F[n] 就可以從 F[0] = 0, F[1] = 1 的初條件開始寫作
接下來你會冪取模的二分法（例如算 2^100 天以後星期幾，就是把 2^100 除以 7 求餘數，不必將 2 乘 100 次的那個方法）的話，把那個方法用於矩陣相乘就好了。
附註 1：不要想著將矩陣對角化，因為 sqrt(5) 在模 10007 的有限域 Z(10007) 裡面是算不出來的（沒有乙個整數平方以後被 10007 除餘數為 5）。即使對角化了還是要算乙個數的 n 次方模 10007 的餘數，和矩陣 n 次方的二分法冪取模時間複雜度都是 O(log2(n)).
附註 2：不要想著觀察週期。乙個二階遞推數列模 10007 的週期上限最長可以達到 10007^2. 所以觀察週期的方法推廣不到大規模的問題。
3樓：
這個結論其實可以推廣為，任意乙個齊次線性的整數遞推數列都是模週期的我們考慮k階常係數齊次線性遞推數列：
這個數列 是整數數列
其中 ， 是常整數，
則對於任意自然數 ，數列 的各項整除以 ，所得餘數成週期數列考慮 元有序陣列
其中 並且 （ ）
這樣的 元陣列至多有 種，所以對於無窮陣列列（ ）必將出現兩個陣列相同
令則由遞推關係
有從而有
這證明了數列 是以 為週期的週期數列（不一定是純週期數列）它從第 項起開始迴圈
要使得 是純週期數列，需要滿足乙個條件
注意到假如
則從而有
即說明從第 項起便開始迴圈
以此類推，可知它從首項起就構成週期數列
回到本題，斐波那契數列的餘數數列當然是純週期數列，因為任何自然數都與1互素
4樓：mcg
整數的加、減、乘運算對運算元的取餘運算，不影響對最終結果取餘。（不過有可能出現負數，所以要把結果+除數做取餘）
也就是說 (a+b-c*d)%f = ((a%f+b%f-(c%f)*(d%f))%f+f)%f
後面那個%f+f)%f 是為了針對減法出現負數，如果沒有減法，直接%f就好，或者假設規定負數取餘結果為正，-2%7=5，那也不需要。要看語法規則。
問，今天周五，2的2020次方天之後，是週幾？
5樓：3Ni2Co
把相鄰兩項 看做乙個數對 ,那麼 可以由 唯一確定,而不同的 最多隻會有 種( 為質數),所以在若干項後一定會出現與之前相同的 ,就進入了迴圈.
其實 這個上界非常松,有結論是最短迴圈節長度不會超過 .
求解斐波那契數列模$p$意義下最短迴圈節 - NamelessOIer - 部落格園
6樓：加油的希望
首先，我們要了解抽屜原理：
將多於n+1（包含）個物體放到n個抽屜裡，則至少有乙個抽屜中有至少兩件物品。
例如，一年中有12個月，任意的13個或更多不同的人中，至少有兩個人在同乙個月出生。
令 表示斐波那契數列第 項 對 取模後的餘數的結果，即先證引理：
證明：設
則（注意此處同餘號與等號的區別）
又因為則
引理成立。
由 的定義可知，
由抽屜原理，對於有序數對集合
集合 中的數對至多有 種組合，則當 時，必定存在一組 ，使得由引理可得
即 數列存在迴圈節。
斐波那契數列可以求和嗎？
水十三 Sn A n 2 1 公式推導如下 斐波那契數列 1 1 2 3 5 8 13 21 An則 a1 1,a2 1,a3 2,a4 3,a5 5,an。求和 Sn a1 a2 a3 AnSn 1 a1 a2 a3 An 1因為a2等於1，所以Sn a2 a1 a2 a3 An 1即 Sn a2...
如何利用單調有界準則證明斐波那契數列前後兩項之比的極限存在？
水之心 設 為 Fibonacci 數列,即 且對任何 有 由此可得對任何 有 記後項與前項之比所構成的數列為 其中 從而有 結論一 0 eeimg 1 對所有 成立.顯然 結論二 的所有奇數項都大於 所有偶數項都小於 證明 由遞推公式可得 故由結論一可知 與 同號.由於 frac eeimg 1 ...
以下是python求斐波那契數列第n項的值是多少，求高手詳釋，真想不通while迴圈裡的邏輯，求詳解？
單爾博 fib的定義 fib n fib n 1 fib n 2 fib n 1 fib n fib n 1 在 式子中 fib n 是 result fib n 1 是 prev resultfib n 2 是 next result在 式子中 fib n 1 是 result fib n 是 p...