Description
Fibonacci數列的遞推公式為：Fn=Fn-1+Fn-2，其中F1=F2=1。

創(chuàng)新互聯建站專注于企業(yè)成都全網營銷推廣、網站重做改版、秭歸網站定制設計、自適應品牌網站建設、H5響應式網站、商城網站制作、集團公司官網建設、外貿網站制作、高端網站制作、響應式網頁設計等建站業(yè)務，價格優(yōu)惠性價比高，為秭歸等各大城市提供網站開發(fā)制作服務。

當n比較大時，Fn也非常大，現在我們想知道，Fn除以10007的余數是多少。

Input
多組測試數據

輸入包含一個整數n。1 <= n <= 1,000,000。

Output
每組輸出一行，包含一個整數，表示Fn除以10007的余數。

Sample Input
10
22

Sample Output
55
7704

利用余數三大定理：

1.余數的加法定理

a與b的和除以c的余數，等于a,b分別除以c的余數之和，或這個和除以c的余數。

即：(a+b)%c = (a%c+b%c)%c

例如：23，16除以5的余數分別是3和1，所以23+16=39除以5的余數等于4，即兩個余數的和3+1.

當余數的和比除數大時，所求的余數等于余數之和再除以c的余數。

例如：23，19除以5的余數分別是3和4，故23+19=42除以5的余數等于3+4=7除以5的余數，即2.

2.余數的乘法定理

a與b的乘積除以c的余數，等于a,b分別除以c的余數的積，或者這個積除以c所得的余數。

即：(a*b)%c = (a%c*b%c)%c

例如：23，16除以5的余數分別是3和1，所以23×16除以5的余數等于3×1=3。

當余數的和比除數大時，所求的余數等于余數之積再除以c的余數。

例如：23，19除以5的余數分別是3和4，所以23×19除以5的余數等于3×4除以5的余數，即2.

3.同余定理

若兩個整數a、b被自然數m除有相同的余數，那么稱a、b對于模m同余，用式子表示為：a≡b ( mod m )，左邊的式子叫做同余式。

同余式讀作：a同余于b，模m。由同余的性質，我們可以得到一個非常重要的推論：

若兩個數a，b除以同一個數m得到的余數相同，則a，b的差一定能被m整除

用式子表示為：如果有a≡b ( mod m )，那么一定有a－b＝mk,k是整數，即m|(a－b)

那么：如果有mk%m=0，b%m=0,就有（mk+b）%m

package 第八次模擬;

import java.util.Scanner;
public class Demo12Fibonacci {
public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 while(sc.hasNext()){
 
 int n = sc.nextInt();
 int []f = new int [n+2];
 int [] count=new int [n+2];
 f[1]=1;
 f[2]=1;
 for (int i = 3; i <=n; i++) {
 f[i]=(f[i-1]+f[i-2]);
 if(f[i]/10007>=1){
 f[i]%=10007; 
 }
 
 }
 System.out.println(f[n]);
 
 } 
 }
}

另外有需要云服務器可以了解下創(chuàng)新互聯建站aaarwkj.com，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

本文標題：Java實現Fibonacci(斐波那契)取余的示例代碼-創(chuàng)新互聯
文章鏈接：http://aaarwkj.com/article2/ccccic.html

成都網站建設公司_創(chuàng)新互聯，為您提供ChatGPT、網站收錄、軟件開發(fā)、云服務器、網站維護、響應式網站

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯