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 \stackrel{Ktimes}{\overbrace{((XmodY)\times 10)}}÷Y\rfloor =\lfloor ((X\times {10}^K)modY)÷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)))$.