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

    solution

    Đề bài: [Toán rời rạc] Truy hồi bình phương theo modulo

    Cho dãy phi tuyến xác định bởi a0a_0a0​ và truy hồi

    an=(an−12+c) mod p.a_{n}=(a_{n-1}^2+c)\bmod p.an​=(an−12​+c)modp.

    Cho a0,c,p,na_0,c,p,na0​,c,p,n, hãy tính ana_nan​. Vì mọi phép tính đều lấy theo modulo ppp, kết quả là xác định. (Với n=0n=0n=0 thì đáp số là a0 mod pa_0\bmod pa0​modp.)

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

      Một dòng chứa bốn số nguyên a0a_0a0​, ccc, ppp, nnn.

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

      0≤a0,c<p≤109+70 \le a_0,c < p \le 10^9+70≤a0​,c<p≤109+7, 0≤n≤1070 \le n \le 10^70≤n≤107.

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

      Một dòng: an mod pa_n \bmod pan​modp.

    Ví dụ:

    Đầu vào:

    2 3 1000000007 2

    Đầu ra:

    52

    Giải thích:

    $a_1=2^2+3=7$, $a_2=7^2+3=52$; với $p$ lớn nên $a_2=52$.

    Đang tải editor...