Hướng dẫn giải của XYZ
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Lời giải
Một số chia hết cho cả ~x~, ~y~, ~z~ khi và chỉ khi nó chia hết cho ~L = \text{lcm}(x, y, z)~. Khi đó ~XYZ(k) = \left\lceil 10^{k-1} / L \right\rceil \cdot L~ nếu giá trị này không vượt quá ~10^k - 1~, ngược lại bằng ~-1~.
Hai điểm cần cẩn thận:
- ~L~ có thể lên tới hơn ~10^{12}~ và ~XYZ(16)~ lên tới gần ~10^{16}~, nên phải dùng số nguyên 64 bit.
- Tổng có thể âm (khi mọi số hạng đều bằng ~-1~). Hãy đưa kết quả về đoạn ~[0, 10^9 + 6]~ trước khi in.
Bình luận