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

    solution

    Đề bài: [An toàn thông tin] Lũy thừa modulo nhanh

    Trong hầu hết các hệ mật mã khóa công khai (RSA, Diffie-Hellman, ElGamal, ...), phép toán nền tảng nhất là lũy thừa modulo: tính ab mod na^b \bmod nabmodn một cách hiệu quả bằng thuật toán bình phương lặp (square-and-multiply), thay vì tính trực tiếp aba^bab (có thể là một số cực lớn) rồi mới lấy modulo.

    Cho ba số nguyên không âm a,b,na, b, na,b,n. Hãy tính ab mod na^b \bmod nabmodn.

    Quy ước: a0=1a^0 = 1a0=1 với mọi aaa (kể cả a=0a = 0a=0); nếu n=1n = 1n=1 thì kết quả luôn bằng 000.

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

      Một dòng duy nhất chứa ba số nguyên a,b,na, b, na,b,n cách nhau bởi khoảng trắng (0≤a,b<101000 \le a, b < 10^{100}0≤a,b<10100, 1≤n<10181 \le n < 10^{18}1≤n<1018).

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

      Một số nguyên duy nhất - giá trị ab mod na^b \bmod nabmodn.

    Ví dụ:

    Đầu vào:

    2 10 1000

    Đầu ra:

    24

    Đầu vào:

    0 0 5

    Đầu ra:

    1

    Đang tải editor...