For the first subtask, it suffices to iterate over all possible 3-tuples or 4-tuples of lattice points in the grid, and to determine whether a rectangle can be formed from these points. Measures can be taken to avoid over-counting by dividing the final result by the number of times that a given rectangle is counted in this process.

Time complexity: $\mathcal{O}((HV{)}^3)$ or $\mathcal{O}((HV{)}^4)$

For the second subtask, we seek to eliminate the redundancy of counting congruent rectangles multiple times. To do this, we must find a method of enumerating all possible rectangles that can fit within the grid, and for each rectangle, calculate $S$, the number of times that it can be translated in the grid. The answer is then the sum of all such $S$.

One way of doing this is to iterate over all non-ordered pairs of points with one point on the top of the grid, and the other on the left of the grid. This fixes one side of the rectangle $L_0$. Next, iterate over all $L_1,L_2,\dots ,L_N$, which are all translations of $L_0$ in the direction orthogonal to $L_0$ that fall on lattice points in the grid. This will enumerate over all rectangles such that the separation between the left-uppermost point and right-uppermost point is $(x,y)$.

To find $L_{i+1}$, apply the translation $(dx,dy)$ to $L_i$, where $dx=\frac{y}{gcd(x,y)}$ and $dy=\frac{x}{gcd(x,y)}$. It can be shown that applying this translation is the smallest translation such that $L_{i+1}$ is different from $L_i$ and is in the directional orthogonal to $L_i$.

Pseudocode:

answer = 0
for x in [1, v)
    for y in [0, h)
        dx is y / gcd(x, y)
        dy is x / gcd(x, y)
        x_i is x + dx
        y_i is y + dy
        while x_i in bounds and y_i in bounds
            add (h - y_i) * (v - x_i) to answer
            add dx to x_i
            add dy to y_i

Diagram:

Time complexity: $\mathcal{O}(HV{\log }^2(min(H,V)))$