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

    solution

    Đề bài: [Kiến trúc máy tính] Hệ số dư (Residue Number System)

    Trong Hệ số dư (Residue Number System – RNS), một số nguyên được biểu diễn bằng bộ phần dư theo các moduli đôi một nguyên tố cùng nhau m1, m2, ..., mk. Phép cộng/nhân thực hiện song song trên từng phần dư.

    Cho hai số a, b và bộ moduli, hãy:

    1. In phần dư của a và của b (mỗi bộ trên một dòng, các giá trị cách nhau dấu cách);
    2. In bộ phần dư của tích a·b (mod từng modulus) trên dòng thứ ba;
    3. Khôi phục giá trị (a·b) mod M (với M = tích các moduli) bằng định lý số dư Trung Hoa và in trên dòng thứ tư.

    Ví dụ

    a = 7, b = 6, moduli 3 5 7: residue(7) = 1 2 0, residue(6) = 0 1 6, residue(42) = 0 2 0, và 42 mod 105 = 42.

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

      Dòng 1: hai số nguyên không âm a b. Dòng 2: số lượng moduli k rồi k moduli (đôi một nguyên tố cùng nhau).

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

      0 ≤ a, b ≤ 10^9; 1 ≤ k ≤ 6; 2 ≤ mi ≤ 1000; các mi nguyên tố cùng nhau từng đôi.

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

      4 dòng như mô tả: residue(a), residue(b), residue(a·b), và (a·b) mod M.

    Ví dụ:

    Đầu vào:

    7 6
3 3 5 7

    Đầu ra:

    1 2 0
0 1 6
0 2 0
42

    Giải thích:

    residue(7)=1 2 0, residue(6)=0 1 6, residue(42)=0 2 0; CRT khôi phục 42 mod 105 = 42.

    Đang tải editor...