h992: 給測驗們的電神
Tags : 快速冪 數學 矩陣快速冪
Accepted rate : 3人/3人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-06-19 19:04

Content

今天有一群測驗們在討論一個題目,我太弱了,但是為了能夠幫助測驗們,決定找一位與測驗們一樣電的人 (你) 來幫忙。題目如下:

費氏數列 $F_1 = F_2 = 1,F_i = F_{i - 1} + F_{i - 2}$,給你 $a, b$,請你輸出 $F_a^{F_{\ b}}$ ($\text{mod }1000000007$)

Input

第一行有一個正整數 $t$,代表測資筆數。

接下來 $t$ 行,每行有兩個正整數 $a, b$,代表請你
求 $F_a^{F_{\ b}}$ ($\text{mod }1000000007$)。

  • $1 \leq t \leq 10^5$
  • $1 \leq a, b \leq 10^9$
Output

對於每筆測資,輸出一個答案。

Sample Input #1
20
8 26
18 57
5 97
1 57
52 42
88 56
59 43
93 46
32 30
19 52
16 73
67 67
28 38
1 86
10 1
76 84
78 80
47 79
72 14
14 24
Sample Output #1
790331169
359321572
166102658
1
950055260
250836789
806410615
674973146
931043730
771737914
845274794
704387550
39595693
1
55
882480730
458787171
468316472
68093815
1680610
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (100%): 3.0s , <10M
Hint :

$100\%:無特別限制$

Tags:
快速冪 數學 矩陣快速冪
出處:
第六屆簡單的小競賽 [管理者: becaido(Caido) ]


ID User Problem Subject Hit Post Date
30889 becaido(Caido) h992
題解
46 2022-06-19 19:27