Hai đèn chùm

Hướng tiếp cận

Hai đèn lặp lại trạng thái (cặp màu) sau mỗi $L=lcm(n,m)$ ngày. Trong một chu kỳ ta đếm số ngày cùng màu, từ đó suy ra số ngày khác màu, rồi định vị ngày thứ $k$ khác màu.

Nhận xét quan trọng

1. Chu kỳ chung: trạng thái hệ thống lặp với chu kỳ $L=lcm(n,m)$. Đặt $g=gcd(n,m)$.
2. Ngày cùng màu: với mỗi màu $c$ xuất hiện trong cả hai dãy, gọi $u$ là vị trí (1-based) trong $a$ và $v$ trong $b$. Ngày $i$ cùng màu $c$ khi:
   • $i\equiv u\left(\mathrm{mod}n\right)$
   • $i\equiv v\left(\mathrm{mod}m\right)$
3. CRT: hệ trên có nghiệm khi và chỉ khi $u\equiv v\left(\mathrm{mod}g\right)$. Khi có nghiệm, có duy nhất một $i\in [1,L]$ thoả mãn (tìm bằng thuật toán Euclid mở rộng).
4. Đếm ngày khác màu: gọi $M$ là số màu chung tạo ra ngày cùng màu trong $[1,L]$. Số ngày khác màu trong một chu kỳ là $L-M$.

Thuật toán

1. Tính $g=gcd(n,m)$, $L=nm/g$.
2. Lập từ điển vị trí $b_j\to j$. Với mỗi $a_i$, kiểm tra có trong $b$ không, nếu có thì thử CRT để lấy ngày $t\in [1,L]$ và thêm vào danh sách matches.
3. Sắp xếp matches. Số ngày khác màu mỗi chu kỳ: $D=L-|matches|$.
4. Số chu kỳ đầy đủ: $\text{full}=\lfloor (k-1)/D\rfloor$. Còn lại: $r=k-\text{full}·D$.
5. Trong một chu kỳ, duyệt qua các đoạn ngày khác màu giữa các phần tử của matches (với $L+1$ làm sentinel) để tìm ngày khác màu thứ $r$. Đáp án là $\text{full}·L+(\text{ngày trong chu kỳ})$.

Độ phức tạp

• Thời gian: $O((n+m)\log (max(n,m)))$ chính cho sắp xếp matches và tra cứu hashmap.
• Bộ nhớ: $O(n+m)$.