BOJ 32765 연봉 998244353원 주세요

주어진 $X$에 대해 $a_0 = X$로 두고, $i$번 사원이 받을 연봉을 $a_i$라고 합시다. 이 문제를 풀기 위해서는 다음의 관찰이 필요합니다.

• $a_i = ki$일 때 $k < i$이면, 모든 $j > i$에 대해서도 $a_j = kj$입니다. $ki$와 $k(i+1)$의 차이는 $k$이고 이는 $i+1$의 배수 두 개의 간격보다 작기 때문입니다.
• 대략 $i \ge \sqrt{2X}$이면 위의 식이 성립합니다. $a_i - a_{i-1} \le i$이고, 이 상한을 모두 더하면 대략 $X + \frac{i^2}{2}$가 되는데 이것이 $i^2$보다 작아지는 시점이 $\sqrt{2X}$ 정도가 됩니다.

따라서, 넉넉잡아 $i = 10^5$까지는 시뮬레이션을 하고, 그 뒤는 첫 번째 성질을 이용해 바로 구할 수 있습니다.