Ta nhận thấy rằng đây là một bài toán mà các subtask gần như không bao trùm lên nhau, vì vậy nên chúng ta sẽ có một thuật toán riêng cho từng subtask (trừ subtask 1 khi thuật toán cho subtask 3) có thể bao quát hết được các test.

Subtask 1

Ta brute force với mỗi query, ta duyệt tất cả các cặp ~i, j~ và thêm ~a_i \% a_j~ vào đáp án cho query này.

Độ phức tạp : ~O(Q \cdot N^2)~

Subtask 2

Nhận thấy rằng số lượng giá trị ~a_i~ khác biệt rất thấp, và chúng ta chỉ quan tâm tới giá trị của ~a_i~ chứ không cần quan tâm tới vị trí của chúng. Từ đó, ta thấy rằng chúng ta có thể tính toán giá trị trong đoạn được query trong ~O(1)~ với mỗi giá trị bằng cách duy trì prefix sum cho chúng. Từ đó, thay vì brute force mọi cặp phần tử thì ta sẽ brute force mọi cặp value và tính contribution vào đáp án.

Độ phức tạp: ~O(N \cdot 10 + 100 \cdot Q) = O(N + Q)~

Subtask 3

Ta nhận thấy rằng do ~Q~ lớn và ~N \leq 1000~, chúng ta có thể precompute giá trị của các query ~l, r~ và trả lời chúng trong ~O(1)~. Để làm được như vậy, ta có thể sử dụng lại đáp án của đoạn nhỏ hơn để tính đáp án cho đoạn lớn hơn. Kỹ thuật này còn được gọi là Rangge DP. Để có bao quát hết trường hợp, ta sẽ sử dụng lại kết quả của ~dp_{l + 1, r}~ và ~dp_{l, r - 1}~. Ta để ý rằng kết quả cho các cặp ~l \leq i, j \leq r~ bị tính lặp lại 2 lần, nên ta có thể trừ đi kết quả của cặp này ra khỏi đáp án. Như vậy, cách xây dựng mảng ~dp~ của chúng ta đã hoàn thành.

Độ phức tạp: ~O(N^2 + Q)~.

Subtask 4

Vì range cho ~a_i \leq 1000~, ta có thể sử dụng lại ý tưởng cho subtask ~2~: lưu frequency của các value thay vì quan tâm tới vị trí của chúng. Ta có thể tận dụng ý tưởng rằng ~a \mod b = a - \lfloor a / b \rfloor \cdot b~, và tính dựa trên công thức này để tính kết quả. Ta có thể duyệt từng ~b~ và từng giá trị phân biệt ~\lfloor a / b \rfloor~ và dùng prefix sum để tính nhanh các ~a~ có cùng giá trị ~\lfloor a / b \rfloor~. Độ phức tạp của việc này nhìn có vẻ là ~O(N^2)~, nhưng thật ra số iterations chỉ là ~\frac{N}{1} + \frac{N}{2} + ... + \frac{N}{N} = O(N \cdot \log N)~. Vậy nên tổng độ phức tạp của chúng ta là ~O(Q \cdot V \log V)~, với ~V = max (A_i)~