A solution that runs in $$$O(t\cdot n)$$$ should easily be fast enough.

First of all, there are $$$n$$$ ways of choosing exactly $$$1$$$ value. We can add this to the answer. Now, every remaining arithmetic progression will have at least $$$2$$$ values.

Recall that an arithmeric progression has a constant difference of consecutive elements, let's call it $$$d$$$. $$$d$$$ can have any value between $$$1$$$ and $$$n - 1$$$. If we can calculate the number of arithmetic progressions for each value of $$$d$$$, we can sum those up and calculate the answer on $$$O(n)$$$.

How to solve the problem for each $$$d$$$? Let's consider an example case $$$n = 10$$$, $$$d = 3$$$. For two numbers to have a difference of $$$d$$$, they must be equivalent modulo $$$d$$$ (i.e. they have the same remainder when divided by $$$d$$$). Let's group the $$$n = 10$$$ numbers based on their remainder modulo $$$d = 3$$$ in ascending order:

0 mod 3: 3 6 9
1 mod 3: 1 4 7 10
2 mod 3: 2 5 8

Now we have $$$d = 3$$$ different arrays of integers. Notice that any continuous subarray of length $$$> 1$$$ of any one of these arrays is an arithmetic progression with $$$d = 3$$$. Also notice, that every possible arithmetic progression of values $$$1..10$$$ with $$$d = 3$$$ is a subarray of length $$$> 1$$$ of one of these arrays. This means that the number of arithmetic progressions with $$$d = 3$$$ is equal to the number of subarrays of length $$$> 1$$$ of these arrays.

How can we calculate the number of subarrays of length $$$> 1$$$ of these arrays? Recall that an array of length $$$k$$$ has exactly $$$\frac{k(k+1)}{2}$$$ subarrays, exactly $$$k$$$ of which have length $$$1$$$. Thus, the number of subarrays of length $$$> 1$$$ is $$$\frac{k(k+1)}{2} - k = \frac{k(k+1)}{2} - \frac{2k}{2} = \frac{k(k+1) - 2k}{2} = \frac{k(k + 1 - 2)}{2}= \frac{k(k-1)}{2}$$$.

Each value of $$$d$$$ creates $$$d$$$ different arrays, we can't just iterate over all of them. How can we find the number of subarrays in all of them efficiently (for fixed $$$d$$$)?

Notice that the integers $$$1, 2, 3, \dots d$$$ all have different remainders modulo $$$d$$$. Thus, they belong to different arrays. The same applies for integers $$$d + 1, d + 2, d + 3, \dots 2d$$$, integers $$$2d + 1, 2d + 2, 2d + 3, \dots 3d$$$ up to $$$(k-1)d + 1, (k-1)d + 2, (k-1)d + 3, \dots kd$$$, where $$$k$$$ is the largest integer satisfying $$$kd \le n$$$. We can see that

$$$kd \le n \Leftrightarrow k \le \frac{n}{d}$$$

The largest integer satisfying this is $$$k = \left\lfloor\frac{n}{d}\right\rfloor$$$. This means that all $$$d$$$ arrays contain at least $$$\left\lfloor\frac{n}{d}\right\rfloor$$$ integers. The remaining $$$n \bmod d$$$ integers all have different remainders modulo $$$d$$$ meaning that they belong to different arrays. This means that $$$n \bmod d$$$ of the $$$d$$$ arrays actually contain $$$\left\lfloor\frac{n}{d}\right\rfloor + 1$$$ integers, and the remaining $$$d - (n \bmod d)$$$ arrays contain $$$\left\lfloor\frac{n}{d}\right\rfloor$$$ integers.

Thus, the number of subarrays of the arrays for a given $$$d$$$ (which equals the number of arithmetic progressions with consecutive difference $$$d$$$) is

$$$\displaystyle(n \bmod d) \cdot \frac{\left(\left\lfloor\frac{n}{d}\right\rfloor + 1\right)\left(\left\lfloor\frac{n}{d}\right\rfloor + 1 - 1\right)}{2} + (d - n \bmod d) \cdot \frac{\left\lfloor\frac{n}{d}\right\rfloor\left(\left\lfloor\frac{n}{d}\right\rfloor - 1\right)}{2}$$$

$$$ = \displaystyle(n \bmod d) \cdot \frac{\left(\left\lfloor\frac{n}{d}\right\rfloor + 1\right)\left\lfloor\frac{n}{d}\right\rfloor}{2} + (d - n \bmod d) \cdot \frac{\left\lfloor\frac{n}{d}\right\rfloor\left(\left\lfloor\frac{n}{d}\right\rfloor - 1\right)}{2}$$$

$$$ = \displaystyle\frac{(n \bmod d)\left\lfloor\frac{n}{d}\right\rfloor\left(\left\lfloor\frac{n}{d}\right\rfloor + 1\right) + (d - n \bmod d)\left\lfloor\frac{n}{d}\right\rfloor\left(\left\lfloor\frac{n}{d}\right\rfloor - 1\right)}{2}$$$

And the answer to the whole problem is $$$n + \displaystyle\sum_{d=1}^{n-1}\frac{(n \bmod d)\left\lfloor\frac{n}{d}\right\rfloor\left(\left\lfloor\frac{n}{d}\right\rfloor + 1\right) + (d - n \bmod d)\left\lfloor\frac{n}{d}\right\rfloor\left(\left\lfloor\frac{n}{d}\right\rfloor - 1\right)}{2}$$$

Please note that we don't need to worry about arrays of length $$$1$$$ or $$$0$$$ messing up our calculations, since the number of subarrays $$$\frac{k(k-1)}{2}$$$ gives the correct answer of $$$0$$$ in both cases.

I am going to refer to "Arithmetic Sequence" here as "AS"

First, handling AS of size $$$1$$$, obviously the answer is $$$N$$$, as there are $$$N$$$ single elements

Now, for any AS $$$T$$$ of Length $$$ ≥ 2$$$, it can be uniquely determined by 3 values, $$$A,n,d$$$, where $$$A$$$ is the value first term in the sequence $$$(T_0)$$$, $$$d$$$ is the common difference $$$(T_{i+1} - T_i)$$$, and $$$n+1$$$ is the number of terms in the AS $$$(T_n$$$ is the last term $$$)$$$

In your problem, the AS must satisfy two conditions :

• The AS is ascending, so $$$d>0$$$

• The elements are integers that belong to the interval $$$[1,N]$$$,so $$$1≤A≤N$$$ and $$$1≤T_n≤N$$$ (note that $$$n+1$$$ here denotes the length of the AS, while $$$N$$$ denotes the input in your problem)

Imagine we are brute forcing on $$$A$$$ and trying to find the summation over each answer for a specific $$$A$$$

$$$T_n$$$ is equivalent to $$$A+dn$$$, since $$$A,d,n≥1$$$, we only need to solve for the number of ways to choose $$$d,n$$$ such that $$$A+dn≤N$$$, or more precisely $$$dn≤N-A$$$

Now we have reduced our problem to this problem :

Given an integer $$$K$$$, find the number of ways to choose two integers $$$x,y$$$ $$$(1≤x,y≤K)$$$ such that $$$xy≤K$$$

There are two ways to approach this problem, one will lead to an $$$O(\sqrt n)$$$ per test case, and another one will be $$$O(n\log \log n)$$$ preprocessing and $$$O(1)$$$ per test case, since $$$N≤10^6$$$ I am going to explain the $$$O(n\log \log n)$$$ solution :

Let the number of ways to choose two integers $$$x,y$$$ $$$(1≤x,y≤Z)$$$ such that $$$xy=Z$$$ be $$$d(Z)$$$, we can see that this is actually equivalent to the number of divisors of $$$Z$$$, The reason is for every valid number $$$x$$$ we choose, there is going to be a unique $$$y$$$ such that $$$xy=Z$$$, OF course valid $$$x$$$ can only be a divisor of $$$Z$$$ (because $$$Z$$$ is a multiple of $$$x$$$)

Now, we can see that the solution to the problem above (with $$$K$$$) is equal to $$$\displaystyle\sum\limits_{Z=1}^{K}d(Z)$$$

And the solution to the original problem is equal to $$$\displaystyle\sum\limits_{A=1}^{N}\sum\limits_{Z=1}^{N-A}d(Z) = \sum\limits_{i=0}^{N-1}\sum\limits_{Z=1}^{i}d(Z)$$$ ($$$N-A$$$ here is donated as $$$i$$$)

So the answer turns out to be a double prefix sum on the array/function $$$d$$$ till $$$N-1$$$, this can be easily precalculated in $$$O(n)$$$ if we already have array $$$d$$$, and it can be easily calculated in $$$O(n\log \log n)$$$ by using prime factorization to find number of divisors of each $$$Z$$$ $$$(1≤Z≤10^6)$$$

If you need any help or clarifications regarding some details feel free to ask