Easy Divisor Problem

Let

$$D(N)=\sum_{x=1}^{N}\tau(x).$$

The value $\tau(x)$ is the number of ordered pairs of positive integers $(a,b)$ satisfying $ab=x$. Therefore

$$D(N)=\#\{(a,b)\in\mathbb Z_{>0}^2:ab\le N\} =\sum_{a=1}^{N}\left\lfloor\frac Na\right\rfloor.$$

Thus the task is to count positive lattice points under the hyperbola $xy=N$.

Subtask 1

For $N\le10^6$, evaluate the sum directly in $O(N)$ time.

Subtask 2

The hyperbola is symmetric about $x=y$. Let $X=\lfloor\sqrt N\rfloor$. Then

$$D(N)=2\sum_{x=1}^{X}\left\lfloor\frac Nx\right\rfloor-X^2.$$

This gives an $O(\sqrt N)$ algorithm, which is fast enough for $N\le10^{12}$.

Full subtask

For $N\le10^{18}$, the square-root method is still too slow. The intended solution uses Richard Sladkey's successive approximation method, which counts the lattice points in $O(N^{1/3})$ time and $O(\log N)$ extra space.

Set

$$X_{\max}=\lfloor\sqrt N\rfloor,\qquad Y_{\min}=\left\lfloor\frac{N}{X_{\max}}\right\rfloor$$

and in the implementation choose

$$X_{\min}=\min\left(X_{\max},\ 2\left\lceil\sqrt[3]{2N}\right\rceil\right).$$

Columns with $x<X_{\min}$ are summed directly, which already costs only $O(N^{1/3})$.

For the remaining part, approximate the hyperbola by integral lines. Let two boundary lines be

$$L_1:a_1x+b_1y=c_1,\qquad L_2:a_2x+b_2y=c_2.$$

Choose their slopes as Farey neighbors, so

$$a_1b_2-a_2b_1=1.$$

Define transformed coordinates

$$u=a_1x+b_1y-c_1,\qquad v=a_2x+b_2y-c_2.$$

Because the determinant is $1$, integer lattice points correspond bijectively. The inverse transform is

$$x=b_2(u+c_1)-b_1(v+c_2),$$ $$y=a_1(v+c_2)-a_2(u+c_1).$$

Solving the transformed hyperbola for $v$ gives

$$V(u)=\frac{(a_1b_2+b_1a_2)(u+c_1)-\sqrt{(u+c_1)^2-4a_1b_1N}}{2a_1b_1}-c_2.$$

Similarly,

$$U(v)=\frac{(a_1b_2+b_1a_2)(v+c_2)-\sqrt{(v+c_2)^2-4a_2b_2N}}{2a_2b_2}-c_1.$$

If one side of a region is small, sum $\lfloor V(u)\rfloor$ or $\lfloor U(v)\rfloor$ directly.

Otherwise take the mediant

$$a_3=a_1+a_2,\qquad b_3=b_1+b_2.$$

The point where the transformed hyperbola has slope $-1$ has

$$u_{\mathrm{tan}}=(a_1b_2+b_1a_2+2a_1b_1)\sqrt{\frac{N}{a_3b_3}}-c_1.$$

Set $u_4=\lfloor u_{\mathrm{tan}}\rfloor$, $u_5=u_4+1$, and

$$v_4=\lfloor V(u_4)\rfloor,\qquad v_5=\lfloor V(u_5)\rfloor,$$ $$v_6=u_4+v_4,\qquad u_7=u_5+v_5.$$

With $\Delta(k)=k(k+1)/2$, the lattice points in the middle polygon are counted in the implementation by

$$\Delta(v_6-1)-\Delta(v_6-u_5)+\Delta(u_7-u_5).$$

The two remaining regions are bounded by $(a_1/b_1,a_3/b_3)$ and , respectively, so the same procedure recurses on both.

At the top level, process the regions corresponding to integral slopes $-1,-2,-3,\ldots$. A slope $-a$ is tangent around $x\approx\sqrt{N/a}$. Stop once this point falls below and finish the short remainder directly. Polygonal parts between consecutive regions are counted with triangular-number formulas.

Sladkey's analysis bounds the total number of visited regions by $O(N^{1/3})$, while the recursion depth is $O(\log N)$. Hence the total time complexity is $O(N^{1/3})$ and the extra space complexity is .

For $N=10^{18}$, the exact value $D(N)$ exceeds signed 64-bit range. Use __int128 for the exact lattice-point count and relevant products, and reduce modulo $998\,244\,353$ only at the end.

Solution written by GPT5.6