Hướng giải của Định Lý Thặng Dư Trung Hoa
Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Định lý Thặng dư Trung Hoa (Chinese Remainder Theorem - CRT) giải hệ phương trình đồng dư: \(x \equiv a_i \pmod{m_i}\) Với \(m_i\) nguyên tố cùng nhau đôi một.
Nghiệm duy nhất \(x \pmod M\) với \(M = m_1 \cdot m_2 \dots m_k\) được tìm bằng công thức: \(x = \sum_{i=1}^k a_i \cdot M_i \cdot y_i \pmod M\)
Trong đó:
- \(M_i = \frac{M}{m_i}\)
- \(y_i = M_i^{-1} \pmod{m_i}\) (nghịch đảo đồng dư thức của \(M_i\) theo modulo \(m_i\), tìm được bằng thuật toán Euclid mở rộng).
Ta thực hiện phép nhân modulo cẩn thận sử dụng kiểu dữ liệu __int128 trong C++ để tránh tràn số khi tích \(M \le 10^{18}\).
Nhận xét