수열의 합 2 출제

2022 SKKU 프로그래밍 대회 in 소프트의 밤에 출제했던 수열의 합 문제의 입력 제한을 $10^7$에서 $10^{14}$로 바꾼 수열의 합 2 문제를 출제했다. 대회 출제 후기에서 언급했듯이 수열의 합은 $\mathcal{O}\left(\sqrt{N}\right)$ 풀이를 생각하고 만든 문제였기 때문에 수열의 합 2를 개인적으로 출제하게 되었다.

기존 수열의 합의 풀이는 풀이 슬라이드에서 확인할 수 있다. 어떤 양의 정수 $d$가 $\sum_{i=1}^{N}{a_i}$에 몇 번 기여하는지 생각하면 $\sum_{i=1}^{N}{a_i}=\sum_{i=1}^{N}{\left(-1\right)^{i}\lfloor\frac{N}{i}\rfloor}$임을 알 수 있다. 이제 $\sum_{i=1}^{N}{\left(-1\right)^{i}\lfloor\frac{N}{i}\rfloor}$를 $\mathcal{O}\left(\sqrt{N}\right)$에 해결해야 한다.

풀이 1

사실 1. $\sum_{i=1}^{N}{\lfloor\frac{N}{i}\rfloor}=2\sum_{i=1}^{\lfloor\sqrt{N}\rfloor}{\lfloor\frac{N}{i}\rfloor}-{\lfloor\sqrt{N}\rfloor}^2$

기하학적 관점에서 $\sum_{i=1}^{N}{\lfloor\frac{N}{i}\rfloor}$ 은 $x>0, y>0, y\le\frac{N}{x}$ 영역에 포함된 격자점의 개수이다.

$A, B, C$ 를 다음과 같이 정의한다.

$A:$ $x>0, y>0, y\le\frac{N}{x}, x\le\sqrt{N}$ 에 포함된 격자점의 개수.

$B:$ $x>0, y>0, y\le\frac{N}{x}, y\le\sqrt{N}$ 에 포함된 격자점의 개수.

$C:$ $x>0, y>0, x\le\sqrt{N}, y\le\sqrt{N}$ 에 포함된 격자점의 개수.

함수 $y=\frac{N}{x}$ 는 $y=x$ 대칭이므로 $\sum_{i=1}^{N}{\lfloor\frac{N}{i}\rfloor}=A+B-C=2A-C$가 성립한다.

$A=\sum_{i=1}^{\lfloor\sqrt{N}\rfloor}{\lfloor\frac{N}{i}\rfloor},C={\lfloor N\rfloor}^{2}$이므로 $\sum_{i=1}^{N}{\lfloor\frac{N}{i}\rfloor}=2\sum_{i=1}^{\lfloor\sqrt{N}\rfloor}{\lfloor\frac{N}{i}\rfloor}-{\lfloor\sqrt{N}\rfloor}^2$이다.

사실 2. $\lfloor\frac{a}{bc}\rfloor=\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor$

링크 참고

풀이.

$f(N) = \sum_{i=1}^{N}{\lfloor\frac{N}{i}\rfloor} = 2\sum_{i=1}^{\lfloor\sqrt{N}\rfloor}{\lfloor\frac{N}{i}\rfloor}-{\lfloor\sqrt{N}\rfloor}^2$

$\sum_{i=1}^{N}{\left(-1\right)^{i}{\lfloor\frac{N}{i}\rfloor}} = 2\sum_{i=1}^{\lfloor\frac{N}{2}\rfloor}{\lfloor\frac{N}{2i}\rfloor}-\sum_{i=1}^{N}{\lfloor\frac{N}{i}\rfloor} = 2\sum_{i=1}^{\lfloor\frac{N}{2}\rfloor}{\lfloor\frac{\lfloor\frac{N}{2}\rfloor}{i}\rfloor}-\sum_{i=1}^{N}{\lfloor\frac{N}{i}\rfloor} = 2 f(\lfloor\frac{N}{2}\rfloor) - f(N)$

$\mathcal{O}\left(\sqrt{N}\right)$의 시간복잡도로 $f(N)$ 을 계산할 수 있으므로 $\sum_{i=1}^{N}{\left(-1\right)^{i}\lfloor\frac{N}{i}\rfloor}$ 또한 $\mathcal{O}\left(\sqrt{N}\right)$에 구할 수 있다.

풀이 2

$\lfloor\frac{N}{1}\rfloor, \lfloor\frac{N}{2}\rfloor, \cdots, \lfloor\frac{N}{N}\rfloor$을 $\mathcal{O}\left(\sqrt{N}\right)$에 순회하는 방법을 사용한다. (링크 참고)

$i, j$에 대해 $\lfloor\frac{N}{i}\rfloor = \cdots = \lfloor\frac{N}{j}\rfloor$이다.

$i, j$의 기우성(parity)이 다른 경우에는 $i$번째 항부터 $j$번째 항까지 모두 소거되므로 무시한다 (합에 $0$을 더한다).

$i, j$가 모두 홀수인 경우에는 합에 $-\lfloor\frac{N}{i}\rfloor$를 더한다.

$i, j$가 모두 짝수인 경우에는 합에 $\lfloor\frac{N}{i}\rfloor$을 더한다.

추가사항

항목 1. $\lvert\sum_{i=S}^{T}{a_i}\rvert\le2^{63}-1$

$\lvert\sum_{i=1}^{N}{a_i}\rvert=\lvert\sum_{i=1}^{N}{\left(-1\right)^{i}\lfloor\frac{N}{i}\rfloor}\rvert\le\sum_{i=1}^{N}{\lfloor\frac{N}{i}\rfloor}=3239062263181054$

$\lvert\sum_{i=S}^{T}{a_i}\rvert=\lvert\sum_{i=1}^{T}{a_i}-\sum_{i=1}^{S-1}{a_i}\rvert\le2 \sum_{i=1}^{N}{\lfloor\frac{N}{i}\rfloor}=6478124526362108\le2^{63}-1$

따라서 C++의 long long 자료형으로 충분히 답을 구할 수 있다.

항목 2. sqrt(double) 함수 사용시 정밀도 문제

$\lfloor\sqrt{N}\rfloor$을 구하기 위해 (long long)sqrt(N)과 같은 방식을 사용할 경우 오차가 발생할 수 있지만 적어도 $10^{14}$이하의 $N$에 대해서는 값을 제대로 구한다 (참고).

관련 문제

• Fraction Floor Sum
• Chopping Carrots (Hard Version)
• Suma
• 잘못 구현한 에라토스테네스의 체
• Optimization is Freaky Fun
• 잘 알려진 합 구하기

마무리

풀이 2의 경우 나눗셈 연산 횟수가 많으며, $i$가 $1$씩 증가하지 않기 때문에 풀이 1과 시간복잡도는 동일하지만 실제로는 더 느리다. 풀이 2에 대해 나눗셈 연산 최적화를 하지 않을경우 풀이 1과 유의미한 시간 차이가 발생한다. 풀이 1에서 식을 정리하는 방법이 마음에 들었기 때문에 풀이 1과 최적화된 풀이 2만 허용하려고 했었다. 그러나 검수 과정에서 $\mathcal{O}\left(\sqrt{N}\right)$의 시간복잡도를 가진다면, 상수 차이로 인해 AC와 TLE가 갈리는 것은 좋은 문제가 아니라는 의견이 있었다. 그래서 제한 시간을 $2$초로 설정하여 $\mathcal{O}\left(\sqrt{N}\right)$ 풀이를 모두 허용하는 것으로 정리되었다.

문제 검수를 해주신 검수자 분들과 플랫폼을 제공해주신 Startlink에 감사의 말씀을 드리고 싶다.