tag: adhoc.

Subtask 1

Vì ~K, X, Y~ nhỏ, nên ta có thể lấy trực tiếp số thứ ~K~ từ ~\frac{X}{Y}~. Để làm được điều này, ta biểu diễn ~\frac{X}{Y}~ dưới dạng kiểu double, rồi nhân nó với ~10^K~, sau đó lấy phần nguyên modulo ~10~ của kết quả.

Subtask 2

Với giới hạn này, ta không thể chia trực tiếp ~\frac{X}{Y}~, vì độ chính xác sẽ quá thấp và sẽ dẫn đến sai số. Thay vào đó, ta tiến hành chia ~\frac{X}{Y}~ theo kiểu "tính tay", với mỗi bước lấy phần dư của ~X~ cho ~Y~ gán cho ~X~, rồi nhân ~X~ với ~10~. Sau ~K~ lần, chữ số thứ ~K~ của ~\frac{X}{Y}~ sẽ chính là phần nguyên của ~\frac{X}{Y}~. Vì mỗi truy vấn ta thực hiện ~K~ lần, nên độ phức tạp sẽ là ~O(Q \times \max(K))~.

Subtask 3

Có thể biểu diễn quá trình "tính tay" bằng công thức sau: ~\lfloor \overbrace{((X \bmod Y) \times 10)} ^ {K \; times} \div Y \rfloor = \lfloor ((X \times 10^K) \bmod Y) \div Y \rfloor~

Ta có thể dễ dàng tính ~10^K~ trong ~\log_2(K)~ bằng cách nhân lũy thừa nhị phân. Vì vậy thuật toán của ta có độ phức tạp là ~O(Q \times \log_2(\max(K)))~.