# Solution bài 3 Round 2 - Cấp số cộng
Một cấp số cộng được xác định khi ta biết số đầu tiên ($a$), và công bội ($d$).

## Subtask 1:
Duyệt qua $O(n)$ giá trị của $a$ và $O(n)$ giá trị của $d$.

Nhận thấy độ dài dãy tối đa là: $t = \left\lfloor\frac{N-a}{d}\right\rfloor + 1$ vì các giá trị nằm trong đoạn $[0,N]$

Vậy, với cặp $(a,d)$ bất kì, ta cộng vào đáp án một lượng $t$ (có $t$ dãy cấp số cộng với độ dài lần lượt là $1,2,3,\dots,t$)

ĐPT: $O(n^2)$

## Subtask 2:
Nhắc lại, ở subtask 1, với $(a,d)$ bất kì, ta cộng vào đáp án $(N-a) / d + 1$.

Ta cố giảm thiểu ĐPT bằng cách chỉ duyệt $O(n)$ giá trị của $d$. Có thể tính được tổng trên mà không cần duyệt $a$ hay không?

Giả sử $N = kd + r (0 \le r < d)$
Quan sát:
- Với $0 \le a \le r \rightarrow$ cộng vào $(k+1) \Rightarrow$ tổng cộng vào là $(k+1)(r+1)$
- Với $r < a \le r+d \rightarrow$ cộng vào $k \Rightarrow$ tổng cộng vào là $kd$
- Với $r+d < a \le r+2d \Rightarrow$ tổng cộng vào là $(k-1)d$
- ...
- Với $r+d.i < a \le r+d(i+1) \Rightarrow$ tổng cộng vào là $(k-i)d$
- ...

Vậy với mỗi $d$, hoàn toàn tính được tổng của các cặp $(a,d)$ trong $O(1)$.

ĐPT: $O(n)$

## Subtask 3:
Ta giải bằng chia căn.

Nhận xét: Công bội càng lớn thì độ dài tối đa của dãy CSC càng bé. Với $d > \sqrt(n)$, độ dài của dãy CSC công bội $d$ không vượt quá $\sqrt{n}$.

Đặt $R = \left\lfloor\sqrt{n}\right\rfloor$. Ta chia làm 2 trường hợp:
- $d \le R$. Tiến hành duyệt $d$ và giải như subtask 2
- $d > R$, ta kết luận độ dài dãy $<R$.
Ta tiến hành duyệt độ dài dãy, đặt là $l,$ $l \in [1,R-1]$. Cần trả lời câu hỏi: "Có bao nhiêu dãy CSC có độ dài $l$?"
Nhận thấy với CSC có độ dài $l$, công bội $d$ thì hiệu giữa giá trị cuối và giá trị đầu là $d(l-1)$. Vì các giá trị giới hạn trong $[0,N]$ nên sẽ có $N-d(l-1)+1$ dãy CSC như vậy.
Vì thế, nếu cố định $l$ thì ta hoàn toàn tính được công bội lớn nhất có thể: $d_{max} = \left\lfloor\frac{N}{l-1}\right\rfloor)$.
Tổng $\Sigma_{d = R+1}^{d_{max}} N-d(l-1)+1$ tính được trong $O(1)$.

Vậy ĐPT tổng là $O(\sqrt(N))$