ブルーブリッジカップアルゴリズム:フィボナッチはFnを10007の余数で割ることを求めます

時間制限:1.0 sメモリ制限:512.0 MB
【問題の説明】Fibonacci数列の繰返し式は、Fn=Fn-1+Fn-2であり、F 1=F 2=1である.nが比較的大きい場合、Fnも非常に大きく、Fnを10007で割った残高がどれだけあるかを知りたい.
【入力フォーマット】入力行には整数nが含まれている.【出力フォーマット】出力行には、条件を満たす数の和を表す整数が含まれている.【サンプル入力】22【サンプル出力】7704【評価例規模と約定】すべての評価例について、1≦n≦1000000.
nが35のとき、すなわち35番目のフィボナッチ数を計算する.
私は3つの方法で法則をテストしました.1つ目は普通のフィボナッチ数列です.2つ目は有限変数でフィボナッチ数列を作り、ここでは%9でテストします.3つ目は1つのtemp変数でフィボナッチ数列の余剰を求める問題である.

		
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		int l1 = 1;
		int l2 = 1;
		//             
		for(int i = 2;i < n;i++) {
     
			l2 = l1 + l2;
			l1 = l2 - l1;
			System.out.print(l2 + " ");
		}
		System.out.println();
		l1 = 1;
		l2 = 1;
		//           
		for(int i = 2;i < n;i++) {
     
			l2 = l1 + l2;
			l1 = l2 - l1;
			l2 %= 10007;
			System.out.print(l2 + " ");
		}
		
		System.out.println();
		l1 = 1;
		l2 = 1;
		//           
		for(int i = 2;i < n;i++) {
     
			int temp = l2;
			l2 = l1 + l2;
			l2 %= 10007;
			l1 = temp;
			System.out.print(l2 + " ");
		}

//   (%9, 25  ):
//     ,     %9  ,           
2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 
2 3 5 8 4 3 7 1 8 0 8 8 7 6 4 1 5 6 2 8 1 0 1 1 2 3 5 8 4 3 7 1 8 
2 3 5 8 4 3 7 1 8 0 8 8 7 6 4 1 5 6 2 8 1 0 1 1 2 3 5 8 4 3 7 1 8 

Fnを直接算出し、Fnを10007で割るといいですが、この数は大きすぎてBigIntegerで貯める必要があり、時間もかかるので、この方式を採用しました.
次の質問は、なぜ1つの数%10007を変えなかったのかということです.
これは、余剰演算には、n%p=(a+b)%p=(a%p+b%p)%pという定理があるためである.
この過程は中間変数のこの方法で説明し、よりよく説明する.私たちが最終的に求めたフィボナッチ数Fn%pは実際には(l 1+l 2)%p、すなわち(l 1%p+l 2%p)%pである.仮に私たちが現在3つの数A B C l 1をAとし、l 2をB.A+B=C tempがこのときのl 2、すなわちB%pに等しいと仮定する.そしてl 2=A+B=Cをさらに10007で割って余りを求める.このときl 2=C%pでl 1=temp=B%pとなり、もう1つDがあるとl 2=(l 1+l 2)%p=(B%p+C%p)%pとなる
この時点で(l 1%p+l 2%p)%p.という書き方になってしまうのではないでしょうか.

		l1 = 1;
		l2 = 1;
		//           
		for(int i = 2;i < n;i++) {
     
			int temp = l2;
			l2 = l1 + l2;
			l2 %= 10007;
			l1 = temp;
			System.out.print(l2 + " ");
		}