No.3038 フィボナッチ数列の周期

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 8
作問者 : testestesttestestest
0 ProblemId : 1314 / 出題時の順位表

問題文

$F_0=0,\ \ F_1=1, \ \ F_i=F_{i-1}+F_{i-2}\ (i\geq2)$ により定められる数列$\{F_i\}$をフィボナッチ数列という。
フィボナッチ数列の$\bmod M$での周期を$10^9+7$で割った余りを求めよ。

入力

N
p_1 k_1
...
p_N k_N

$M$は素因数分解された形で与えられ、$M=\prod p_i^{k_i}$である。
$1\leq N\leq 1000$:整数
$2\leq p_i \leq 10^7$:素数であり、相異なる
$1\leq k_i \leq 1000$:整数

テストケースは全部で25個ある。
1smallから始まる7つのテストケースは$M\leq 10^7$を満たす(★2くらい)
2medから始まる9つのテストケースは$N\leq 20$かつ全ての$i$について$p_i\leq10^6,\ k_i=1$を満たす(★3くらい)
3largeから始まる9つのテストケースには追加制約はない(★4くらい)

出力

フィボナッチ数列の$\bmod M$での周期を$10^9+7$で割った余りを出力せよ。
ただし、「フィボナッチ数列$\{F_i\}$の$\bmod M$での周期」とは次の条件を満たすような正整数$n$のうち最小のものを指す。
条件:ある非負整数$A$が存在して、$A$以上の任意の整数$B$に対して$F_{B+n}=F_{B} \bmod M$が成り立つ

サンプル

サンプル1
入力
2
2 2
3 1
出力
24

$M=2^2 \cdot 3^1=12$である。OEISのA001175によると、mod 12での周期は24になるらしい。
実際に計算すると$0,1,1,2,3,5,8,1,9,10,7,5,0,5,5,10,3,1,4,5,9,2,11,1,0,1,1,\ldots$となり確かに$F_{n+24}=F_n$となっている。
このケースはsmallの追加制約を満たす。

サンプル2
入力
2
97 1
103093 1
出力
10103212

mod 10^7+21での周期は10103212になるらしい。
このケースはmedの追加制約を満たす。

サンプル3
入力
2
9999937 2
9999761 2
出力
650542141

mod 9999396012131709055946713249における周期は96148038578019322985423540になるらしい。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。