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] Định lý số dư Trung Hoa

    Định lý số dư Trung Hoa (CRT) được dùng để tăng tốc giải mã RSA (thuật toán CRT-RSA) và trong nhiều sơ đồ chia sẻ bí mật (secret sharing).

    Cho kkk đồng dư thức dạng

    x≡a1(modm1),x≡a2(modm2),…,x≡ak(modmk)x \equiv a_1 \pmod{m_1}, \quad x \equiv a_2 \pmod{m_2}, \quad \ldots, \quad x \equiv a_k \pmod{m_k}x≡a1​(modm1​),x≡a2​(modm2​),…,x≡ak​(modmk​)

    trong đó các mim_imi​ đôi một nguyên tố cùng nhau. Hãy tìm số nguyên xxx nhỏ nhất thỏa mãn 0≤x<M0 \le x < M0≤x<M, với M=m1⋅m2⋯mkM = m_1 \cdot m_2 \cdots m_kM=m1​⋅m2​⋯mk​, sao cho xxx thỏa mãn đồng thời tất cả các đồng dư thức trên.

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

      Dòng đầu tiên chứa số nguyên kkk (1≤k≤201 \le k \le 201≤k≤20). kkk dòng tiếp theo, mỗi dòng chứa hai số nguyên ai,mia_i, m_iai​,mi​ cách nhau bởi khoảng trắng (1≤mi≤1091 \le m_i \le 10^91≤mi​≤109, 0≤ai<mi0 \le a_i < m_i0≤ai​<mi​). Các giá trị mim_imi​ đôi một nguyên tố cùng nhau.

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

      Một số nguyên duy nhất - nghiệm xxx nhỏ nhất thỏa 0≤x<M0 \le x < M0≤x<M.

    Ví dụ:

    Đầu vào:

    2
2 3
3 5

    Đầu ra:

    8

    Đầu vào:

    1
2 5

    Đầu ra:

    2

    Đang tải editor...