小時候睡不著覺的時候，媽媽就教我們數數，$0,1,1,2,3,5,8,13,21,34,55,89,144,\dots$一直數下去，直到我們睡著。多麼溫馨的畫面啊！
想必大家做的和Fibonacci有關的題目數不勝數，大多是給一個模m，然後再給一個n，叫你求第n項Fibonacci數字。
你總是不厭其煩的敲打著同樣的計算Fibonacci數字的程式，因為那樣可以讓你多AC一題，自己也會十分開心。
重重複複的寫相同的一個程式真是太無趣了，是時候來做個了結了。
希望你做了這題之後，能夠對Fibonacci有一個更深的了解，沉醉在數論的海洋中……
以此紀念Fibonacci，以此紀念逝去的青春。
這裡，為了不引起歧義，我們先定義一遍Fibonacci數列。
\[
F_n=\begin{cases}
n, & n=0,1 \\
F_{n-1}+F_{n-2}, & n \geq 2
\end{cases}
\]
大家都會使用矩陣乘法以及快速冪來解決這個問題。快速冪，一種辦法就是把冪寫成二進制的形式，然後答案就可以用多個二的次冪的和來表示。
那麼，為了方便起見，我們就把要求的Fibonacci項鎖定為二的次冪好了。
於是有了本題。
給定$n$和$m$，叫你求
\[F_{2^n} \mod m\]
第一行是一個正整數$T(1\leq T\leq 100)$，代表測資筆數。
接下來$T$行，每行兩個正整數$n(1\leq n\leq 10^{18})$和$m(1\leq m\leq 10^{18})$。
3 1 1000000007 2 1000000007 3 1000000007
1 3 21
測資1：$n \leq 20$
測資2：$m \leq 10^6$
測資3：$m$是質數。
測資4：$m \leq 10^9$
測資5：$m \leq 10^{15}$
測資6-10：$m \leq 10^{18}$
這是【我愛Möbius】系列的第二題，上一題是【我愛Möbius】之互質對，下一題是【我愛Möbius】之最大公約數求和。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||