Trò chơi đồng dư

Hướng tiếp cận

Bài toán đặt ra điều kiện đủ để xác định $xmodk$ thông qua tập các giá trị $xmod{c}_i$. Đây là ứng dụng trực tiếp của định lý số dư Trung Hoa (CRT).

Nhận xét quan trọng

1. Biết $xmod{c}_i$ tương đương với biết $xmod{p}^a$ với mọi luỹ thừa nguyên tố $p^a\mid c_i$. Đây chính là phát biểu CRT.
2. Do đó tập tri thức của Arya là tập các luỹ thừa nguyên tố $p^a$ mà $p^a\mid c_i$ với một $i$ nào đó. Nói cách khác, Arya biết $xmodm$ với mọi $m$ là ước của ${lcm}_{i}gcd(c_i,k)$.
3. Để xác định $xmodk$, ta cần ${lcm}_{i}gcd(c_i,k)=k$. Tức là, với mỗi luỹ thừa nguyên tố $p^a$ chia hết $k$, phải tồn tại $c_i$ sao cho $p^a\mid c_i$.

Thuật toán

1. Khởi tạo $L=1$.
2. Với mỗi $c_i$:
   • Tính $g_i=gcd(c_i,k)$.
   • Cập nhật $L\leftarrow lcm(L,g_i)$.
3. Nếu $L=k$, in Yes; ngược lại in No.

Giá trị $L$ luôn là ước của $k$ (vì là $lcm$ của các ước của $k$), nên không vượt quá $k$ — không có lo ngại về tràn số.

Độ phức tạp

• Thời gian: $O(n\log k)$ cho các phép tính $gcd$.
• Bộ nhớ: $O(1)$ ngoài đầu vào.