Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Toán cho CNTT] Số Fibonacci bằng lũy thừa ma trận

    Dãy Fibonacci: F0=0F_0=0F0​=0, F1=1F_1=1F1​=1, Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2}Fn​=Fn−1​+Fn−2​. Ta có (Fn+1FnFnFn−1)=(1110)n\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}=\begin{pmatrix}1&1\\1&0\end{pmatrix}^{n}(Fn+1​Fn​​Fn​Fn−1​​)=(11​10​)n. Cho số nguyên nnn và số nguyên ppp, hãy tính Fn mod pF_n \bmod pFn​modp bằng lũy thừa nhanh của ma trận (1110)\begin{pmatrix}1&1\\1&0\end{pmatrix}(11​10​) theo modulo ppp.

    • Định dạng đầu vào:

      Một dòng chứa hai số nguyên n pn\ pn p.

    • Ràng buộc đầu vào:

      0≤n≤10180 \le n \le 10^{18}0≤n≤1018, 2≤p≤1092 \le p \le 10^{9}2≤p≤109.

    • Định dạng đầu ra:

      In ra Fn mod pF_n \bmod pFn​modp, một số nguyên trong đoạn [0,p−1][0,p-1][0,p−1].

    Ví dụ:

    Đầu vào:

    0 5

    Đầu ra:

    0

    Đang tải editor...