f798: 費氏數列第N項
Tags : 大數 費氏數列
Accepted rate : 5人/31人 ( 16% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-05-07 17:48

Content

給你n和m

請你計算 : 費氏數列fib的第n項 mod m

fib[0] = 1

Input

多筆測資

每行兩個數字n和m

0 <= n <= 264 - 1

1 <= m <= 264 - 1

 

Output

請你對每行計算fib[n] mod m

Sample Input #1
0 100
1 150
2 200
3 1000000000000000000
4 10
5 10
Sample Output #1
1
1
2
3
5
8
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 0.1s , <1K
公開 測資點#1 (10%): 0.3s , <1M
公開 測資點#2 (10%): 0.7s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 6.0s , <10M
公開 測資點#5 (10%): 6.0s , <10M
公開 測資點#6 (10%): 7.0s , <10M
公開 測資點#7 (10%): 8.0s , <10M
公開 測資點#8 (10%): 9.0s , <10M
公開 測資點#9 (10%): 0.1s , <1K
Hint :

時限和記憶體限制放很寬,只要算法正確不用優化IO也能AC

O(T * log(n))

怕有些人不知道 C++有一個型態叫做__int128,支援128bit的有號整數運算

Tags:
大數 費氏數列
出處:
老鼠 [管理者:
fire5386 (皮卡丘)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」