Easy Divisor Problem

$D(N)$을 다음과 같이 쓰자.

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

$\tau(x)$는 $ab=x$를 만족하는 양의 정수 순서쌍 $(a,b)$의 개수이다. 따라서

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

즉, 문제는 쌍곡선 $xy=N$ 아래의 양의 정수 격자점 수를 세는 문제이다.

서브태스크 1

$N\le10^6$이면 위 합을 그대로 계산할 수 있다. 시간 복잡도는 $O(N)$이다.

서브태스크 2

쌍곡선은 $x=y$에 대해 대칭이다. $X=\lfloor\sqrt N\rfloor$라 하면

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

따라서 $O(\sqrt N)$에 계산할 수 있고, $N\le10^{12}$에서는 충분하다.

전체 서브태스크

$N\le10^{18}$에서는 $O(\sqrt N)$도 충분하지 않다. 정해는 Richard Sladkey의 successive approximation 방법을 사용하여 격자점 수를 시간, 추가 공간에 계산한다.

먼저

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

를 두고, 구현에서는

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

로 둔다. $x<X_{\min}$인 열은 직접 합산한다. 이 부분은 $O(N^{1/3})$이다.

나머지 부분에서는 쌍곡선에 가까운 정수 직선들을 이용해 영역을 나눈다. 두 경계 직선을

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

라 하자. 기울기들이 Farey neighbor가 되도록 잡아

$$a_1b_2-a_2b_1=1$$

을 만족시킨다.

새 좌표를

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

로 정의하면 행렬식이 $1$이므로 정수 격자점이 일대일 대응한다. 역변환은

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

이다.

이 좌표에서 쌍곡선 위의 $v$를 $u$의 함수로 풀면

$$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.$$

마찬가지로

$$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.$$

영역의 너비나 높이가 작은 경우에는 $\lfloor V(u)\rfloor$ 또는 $\lfloor U(v)\rfloor$를 직접 더한다.

그렇지 않으면 mediant

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

를 사용한다. 새 좌표에서 기울기가 $-1$인 접점의 $u$좌표는

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

이다. $u_4=\lfloor u_{\mathrm{tan}}\rfloor$, $u_5=u_4+1$로 두고

$$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$$

를 계산한다.

$\Delta(k)=k(k+1)/2$라 하면 가운데 다각형의 격자점 수는 구현에서

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

로 계산할 수 있다. 남은 두 영역은 각각 $(a_1/b_1,a_3/b_3)$와 를 경계로 하므로 같은 함수를 재귀 호출한다.

최상위에서는 기울기 $-1,-2,-3,\ldots$에 해당하는 영역을 차례로 처리한다. 기울기 $-a$ 부근의 접점은 $x\approx\sqrt{N/a}$이므로, 이 되면 중단하고 남은 짧은 부분을 직접 계산한다. 각 단계의 삼각형 부분은 삼각수로 즉시 더할 수 있다.

이 방법이 방문하는 전체 영역 수는 $O(N^{1/3})$이고 재귀 깊이는 $O(\log N)$이다. 따라서 전체 시간 복잡도는 $O(N^{1/3})$, 추가 공간 복잡도는 이다.

$N=10^{18}$이면 $D(N)$ 자체는 signed 64-bit 범위를 넘을 수 있다. 정답을 정확히 세는 중간 합에는 __int128을 사용하고, 마지막에만 $998\,244\,353$으로 나눈다. 쌍곡선과 제곱근 판정에 필요한 곱셈도 __int128으로 계산한다.

Solution written by GPT5.6