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] Tính tổng nhiều bên (secure aggregation)

    Tính tổng an toàn nhiều bên

    Mỗi bên PiP_iPi​ có một giá trị riêng viv_ivi​ và tách nó thành các mảnh cộng tính mod mmm. Khi mọi bên công bố các mảnh, tổng tất cả mảnh chính là tổng các bí mật:

    ∑ivi≡∑i∑jrij(modm)\sum_i v_i \equiv \sum_i \sum_j r_{ij} \pmod m∑i​vi​≡∑i​∑j​rij​(modm)

    mà không lộ từng viv_ivi​ riêng lẻ. Cho ma trận mảnh của các bên, hãy tính tổng chung mod mmm.

    Ví dụ

    2 bên: bên 1 có mảnh {10,20}\{10,20\}{10,20}, bên 2 có {5,15,5}\{5,15,5\}{5,15,5}, tổng =55 mod m= 55 \bmod m=55modm.

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

      Dòng 1: m P. Tiếp theo P dòng, mỗi dòng bắt đầu bằng số mảnh q rồi q mảnh.

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

      1≤P≤1001 \le P \le 1001≤P≤100, 2≤m≤10182 \le m \le 10^{18}2≤m≤1018, mỗi q≥1q \ge 1q≥1.

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

      Một số nguyên trong [0,m)[0,m)[0,m): tổng chung.

    Ví dụ:

    Đầu vào:

    100 2
2 10 20
3 5 15 5

    Đầu ra:

    55

    Giải thích:

    Tổng mọi mảnh $= 10+20+5+15+5 = 55$; $55 \bmod 100 = 55$.

    Đang tải editor...