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

    solution

    Đề bài: [Toán cho CNTT] Dãy hồi quy tuyến tính bậc hai theo modulo

    Cho dãy nguyên xác định bởi x0,x1x_0, x_1x0​,x1​ và công thức xk=a⋅xk−1+b⋅xk−2x_k=a\cdot x_{k-1}+b\cdot x_{k-2}xk​=a⋅xk−1​+b⋅xk−2​ với k≥2k\ge 2k≥2 (a,ba,ba,b nguyên cho trước). Đặt vk=(xkxk−1)v_k=\begin{pmatrix}x_k\\x_{k-1}\end{pmatrix}vk​=(xk​xk−1​​), ta có vk=Mvk−1v_k=Mv_{k-1}vk​=Mvk−1​ với M=(ab10)M=\begin{pmatrix}a&b\\1&0\end{pmatrix}M=(a1​b0​). Dùng lũy thừa nhanh ma trận theo modulo ppp để tính xn mod px_n \bmod pxn​modp với nnn có thể rất lớn.

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

      Một dòng chứa 6 số nguyên: a b x0 x1 n pa\ b\ x_0\ x_1\ n\ pa b x0​ x1​ n p.

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

      ∣a∣,∣b∣,∣x0∣,∣x1∣≤109|a|,|b|,|x_0|,|x_1| \le 10^{9}∣a∣,∣b∣,∣x0​∣,∣x1​∣≤109, 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 xn mod px_n \bmod pxn​modp, một số nguyên trong đoạn [0,p−1][0,p-1][0,p−1].

    Ví dụ:

    Đầu vào:

    1 1 0 1 10 1000

    Đầu ra:

    55

    Đang tải editor...