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] Merkle: tính gốc cây băm

    Cây Merkle dùng trong chữ ký hậu lượng tử (Merkle/XMSS) gộp các lá bằng hàm băm. Ở đây dùng hàm gộp xác định:

    h(traˊi,phải)=(traˊi⋅1000003+phải) mod M.h(\text{trái}, \text{phải}) = (\text{trái}\cdot 1000003 + \text{phải}) \bmod M.h(traˊi,phải)=(traˊi⋅1000003+phải)modM.

    Với n=2hn=2^hn=2h lá, gộp từng cặp liên tiếp lên đến khi còn một nút — đó là gốc Merkle.

    Ví dụ: lá (1,2)(1,2)(1,2), M=109+7M=10^9+7M=109+7: gốc =(1⋅1000003+2)=1000005=(1\cdot 1000003 + 2)=1000005=(1⋅1000003+2)=1000005.

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

      Dòng 1: n M (n là luỹ thừa của 2). Dòng 2: n số nguyên là các lá.

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

      n∈{1,2,4,8,16,… }n \in \{1,2,4,8,16,\dots\}n∈{1,2,4,8,16,…}, n≤1024n \le 1024n≤1024; 2≤M≤109+72 \le M \le 10^9+72≤M≤109+7; lá trong [0,M)[0, M)[0,M).

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

      Một số nguyên: gốc Merkle.

    Ví dụ:

    Đầu vào:

    2 1000000007
1 2

    Đầu ra:

    1000005

    Giải thích:

    Gốc = (1·1000003 + 2) mod (10^9+7) = 1000005.

    Đang tải editor...