No.3038 フィボナッチ数列の周期
testestest問題文
$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になるらしい。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。