LiveArchive 6468 Pisano Periods

問題
フィボナッチ数列の mod M をとる。数列で出来る周期の長さを求めよ。
フィボナッチ数列が 0 からはじまるものと考えた時、周期ははじめから見て次に 0, 1 が現れるときで区切れる。（部分列の最後が 1, 0 であるともみれる）

反省
適当な数値や素数を用いて周期の長さが求まるまでのループ回数を調べてみる。すると単純な計算なら間に合うだろうと予想がつくので、以下の愚直なコードでTLEにならないようである。コンテスト中にはその事実に気づかなかった。

メモ
英文の意味をとると、0 から始まるフィボナッチを想像して初めに 0, 1 が来るタイミングで切れると気がついた。MOD のフィボナッチの性質はただのストーリー or まやかしだと考えた。しかし計算量のために工夫された解法を考えていたが、よく分からなかったので取り敢えず愚直な記述をして小さいケースで試そうと考えた。10 の入力で 60 が出力されて、まやかしと考えた性質の一番下の式に当てはまらないのでは？と考えて、初めに 0, 1が来るタイミングでほんとうに良いのかと疑念を抱いた。そこから進捗はなく1時間程度は経って別の人にも読んでもらった。チームの人に 10 の入力の時は自分が見ていた式と違う式を適用するものだと教えてくれた。それで納得し、最大ケースを試した。最大ケースの処理は一瞬であったが、大きい素数の処理はどうかと考えた。素数の処理には多少の時間がかかってしまったので愚直の解法では間違いと思い提出を退けてしまった。

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX (1000000)
#define LIMIT (5*MAX)
int fibs[LIMIT];
 
int main() {
 
  int P; scanf("%d", &P);
 
  while(P--) {
     
    fibs[0] = fibs[1] = 1;
     
    int Tcnt, M;
    scanf("%d %d", &Tcnt, &M);
 
    int ans;
    for(int i=2; ; i++) {
      fibs[i] = (fibs[i-1]+fibs[i-2])%M;
     
      if(fibs[i-2]%M == 1 && fibs[i-1] == 0) {
        ans = i; break;
      }
    }
    printf("%d %d\n", Tcnt, ans);
  }
   
  return 0;
}