白駿2749号:フィボナッチ数3

質問:https://www.acmicpc.net/problem/2749
1st Thinking)
これはn番目にフィボナッチ数を求める問題である.でも….そのnの範囲は相当する.
nは1兆円以下の自然数である.
まず、その資料型の有無符号long long型を扱うことができる.だから入力はまずusigned long longで解決することができます.
しかし、繰り返し文をnの最低価格に調整すると、、、タイムアウトする可能性がありますが、私はもう試しました.

私はやはり私だと思っていた.
2nd Thinking)
i 2番目のフィボナッチ数があると仮定する.
(i次フィボナッチ数)+(i+1次フィボナッチ数)=(i+2次フィボナッチ数).
ここで私が注目しているのは、問題の中で条件として提出された対応する文です.
出力フィボナッチ数を10万の残数で割った.
計算が100000未満のものなので、一定の周期で繰り返すのは、必ずしもnのその広い範囲を繰り返す必要はありませんが、n個のナットを繰り返す周期によって知ることもできますよね?
したがってnを10003000程度に制御し,nのフィボナッチ数に出力する.それから、同じ値段があるかどうか見たいかもしれませんが...

いいえ、ありません.
それ以外に、私は何も知ることができないようなので、他の人の解答を見てから勉強することにしました.
Answer)
ピサノサイクルを参考にして解決できる問題だそうです.
ピザ黄酒とは何ですか.
In number theory, the nth Pisano period, written as π(n), is the period with which the sequence of Fibonacci numbers taken modulo n repeats. - https://en.wikipedia.org/wiki/Pisano_period
そうだそうです.すなわち,整数論でフィボナッチ数にモード乗算を適用すると,フィボナッチ数は一定の周期で繰り返される.証明よりも、Well-Knownはこのような考えを受け入れるべきだ.
10万に分かれた残りの部分については、ピサノサイクルを15万と呼ぶ.だからピサノサイクルを利用して解答しました.

学習のポイント)

整数論からWell-Knownのピサノ周期

まで

サイクルを探している間に、コンピュータを基準にして、十分な数を入力して、

を理解してください.
Code)

#include <iostream>
#include <string.h>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
#include <list>

using namespace std;

int main()
{

	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int arr[1500010];

	unsigned long long n;

	cin >> n;

	arr[0]=0;
	arr[1]=1;
	int temp;

	for (unsigned long long i = 2; i <=1500000; i++)
	{
		arr[i] = arr[i-1] + arr[i-2];
		arr[i]%=1000000;
	}

	cout << arr[n%1500000];
}