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] Chia sẻ cộng tính – Khôi phục theo modulo

    Chia sẻ bí mật cộng tính

    Bí mật sss được chia thành nnn mảnh cộng tính trên Zm\mathbb{Z}_mZm​:

    s≡(r1+r2+⋯+rn)(modm)s \equiv (r_1 + r_2 + \dots + r_n) \pmod ms≡(r1​+r2​+⋯+rn​)(modm)

    Khôi phục = cộng tất cả mảnh rồi lấy modulo mmm.

    Ví dụ

    m=100m=100m=100, mảnh 30,40,3530,40,3530,40,35: s=105 mod 100=5s = 105 \bmod 100 = 5s=105mod100=5.

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

      Dòng 1: m n. Dòng 2: n mảnh.

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

      1≤n≤1001 \le n \le 1001≤n≤100, 2≤m≤10182 \le m \le 10^{18}2≤m≤1018, 0≤ri<m0 \le r_i < m0≤ri​<m.

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

      Một số nguyên trong [0,m)[0, m)[0,m): bí mật sss.

    Ví dụ:

    Đầu vào:

    100 3
30 40 35

    Đầu ra:

    5

    Giải thích:

    $30+40+35=105$, $105 \bmod 100 = 5$.

    Đang tải editor...