試題 入門訓練 Fibonacci數列（Java）

題目：

一開始我看到這題目其實覺得挺簡單的，第一次簡單寫了一個循環就送出上去了，結果…

我意識到這是因為超過long類型的最大範圍導緻的，是以第二次換成BigInteger大整數類型，但最後一個測試點逾時了…

通過百度的大佬們得到了正确地解決方案，那就是——同餘定理。

簡單應用：

• (a + b)%c=(a%c + b%c)%c;

• (a * b)%c=(a%c * b%c)%c；

代碼：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int preSum,rearSum,tmpSum,i=1;
        preSum=rearSum=i;
        if (n>2) {
            i=2;
            while(i!=n) {
                tmpSum=(rearSum+preSum)%10007;
                preSum=rearSum;
                rearSum=tmpSum;
                i++;
            }
        }
        System.out.println(rearSum);
    }
}
           

沒想到第一道題想要拿滿分都需要這麼波折了，代碼之路任重而道遠。