백준 온라인 저지 - 16141. 정수론과 응용: 레시테이션

https://www.acmicpc.net/problem/16141

16141번: 정수론과 응용: 레시테이션

 

재밌는 breaktrough가 있어서 블로그에 옮긴다.

 

 

 

 

(풀이)

 

우선 아래 식부터 정리한다.

$$ \begin{align*} \sum_{m=1}^n \varphi(m, u) &= \sum_{m=1}^n \left(\sum_{k_1=1}^m \cdots \sum_{k_u=1}^m [\gcd(k_1, \dots, k_u, m) = 1] \right) \\ &= \sum_{m=1}^n \sum_{k_1=1}^m \cdots \sum_{k_u=1}^m \left(\sum_{t|gcd(\cdots)} \mu(t) \right) \\ &= \sum_{t \geq 1} \sum_{t|m} \mu(t) \cdot \left\lfloor \frac{m}{t} \right\rfloor^u \\ &= \sum_{t \geq 1} \mu(t) \cdot \left(\sum_{i=1}^{\lfloor n / t \rfloor} i^u \right) \end{align*} $$

 

그러므로 구해야하는 식은 아래와 같이 정리된다.

$$ \begin{align*} \sum_{m=1}^n \sum_{u=1}^v \varphi(m, u) &= \sum_{u=1}^v \sum_{m=1}^n \varphi(m, u) \\ &= \sum_{u=1}^v \sum_{t \geq 1} \mu(t) \cdot \sum_{i=1}^{\lfloor n/t \rfloor} i^u \\ &= \sum_{t \geq 1} \mu(t) \cdot \left(\sum_{i=1}^{\lfloor n/t \rfloor} \sum_{u=1}^v i^u \right) \\ &\triangleq \sum_{t \geq 1} \mu(t) \cdot S(\lfloor n/t \rfloor) \end{align*} $$

 

여기서 함수 $S(m)$는 아래와 같이 정의된 것이다.

$$ S(m) = \sum_{i=1}^m \sum_{u=1}^v i^u $$

 

놀랍게도, 집합 $\{ \lfloor n/1 \rfloor, \lfloor n/2 \rfloor, \lfloor n/3 \rfloor, \dots, \lfloor n/n \rfloor \}$의 크기는 고작해야 $O(\sqrt{n})$이다. 이들을 크기가 큰 것에서 작은 순서대로(감소하는 순서대로) $\{p_1, p_2, \dots, p_f\}$이라고 하고,

$$ \begin{align*} l_i &= \min\{t : \lfloor n/t \rfloor = p_i\} \\ r_i &= \max\{t : \lfloor n/t \rfloor = p_i\} \end{align*} $$

로 정의하면, 아래 관계가 성립함은 어렵지 않게 보일 수 있다.

$$ \begin{gather*} l_1 = 1 \\ r_i = \lfloor n / \lfloor n / l_i \rfloor \rfloor \\ l_{i+1} = r_i + 1 \\ \bigsqcup_i \hspace{2px}[l_i, r_i] = \{1, 2, \dots, n\} \end{gather*} $$

 

구해야하는 식을 아래와 같이 정리한다. (단, 편의상 $p_{f+1} \triangleq 0$으로 둔다.)

$$ \begin{align*} \sum_{t \geq 1} \mu(t) \cdot S(\lfloor n/t \rfloor)&= \sum_{i=1}^f \sum_{l_i \leq t \leq r_i} \mu(t) \cdot S(p_i) \\ &= \sum_{i=1}^f \left(S(p_i) - S(p_{i+1}) \right) \cdot \sum_{t=1}^{r_i} \mu(t) \end{align*} $$

 

첫 번째, 뫼비우스 함수의 $n$항까지의 누적합($\triangleq s_{\mu}(n)$)은 Dirichlet Convolution을 이용하면 구할 수 있다. $n \geq 1$에 대해서,

$$ \begin{align*} \sum_{i=1}^n \sum_{j|i} \mu(j)&= \sum_{i=1}^n [i = 1] = 1 \\ &= \sum_{i=1}^n \sum_{j|i} \mu \left( \frac{i}{j} \right) \\ &= \sum_{j \geq 1} \sum_{k=1}^{\lfloor n/j \rfloor} \mu(k) = \sum_{j \geq 1} s_{\mu}(\lfloor n/j \rfloor) \\ &= s_\mu (n) + \sum_{j \geq 2} s_\mu (\lfloor n/j \rfloor) \end{align*} $$

$$ \begin{align*} \therefore s_\mu(n) &= 1 - \sum_{j \geq 2} s_\mu(\lfloor n/j \rfloor) \\ &= 1 - \sum_{i=2}^f (r_i - l_i + 1) \cdot s_\mu(p_i) \end{align*} $$

따라서 $s_\mu$에 대한 재귀를 이용하고, 입력 $10^6$ 정도 이하인 수에 대해서는 전처리를 해준다면 꽤 빠른 시간 안에 $s_\mu$를 계산한다. 또한 모든 입력이 $\lfloor n / x \rfloor$ 꼴으로 들어오기 때문에 메모이제이션을 해주면 확실한 이득을 볼 수 있다.

 

이제 $S(m)$를 계산한다. 문제를 보면 $n$의 제한은 크지만($10^9$), $v$의 제한은 작다는 것을($10^2$) 안다.

 

수학적 귀납법을 이용하면 $S(m)$이 $m$에 대한 $v+1$차 다항식으로 표현된다는 것을 쉽게 보일 수 있다. 즉, $v+2$개의 좌표 값을 알면 Lagrange interpolation으로 임의의 $x$좌표 $m$에 대한 함수값 $S(m)$을 구할 수 있게 된다. (이 부분이 재밌었다.)

$$ \begin{gather*} S(x) = \sum_{i=1}^{v+1} S(x_i) \cdot \prod_{j \neq i} \frac{x - x_j}{x_i - x_j} \end{gather*} $$

편의상 $x_i = i$로 두고 $S(1), S(2), \dots, S(v+1)$까지만 미리 계산해두면 된다. (그래프가 $(0, 0)$을 지나므로 $v+2$번째 점을 그것으로 두자.)

 

입력값에 상관 없이 일정한 상수들을 모두 계산해두고, 모듈러 나머지의 역연산을 이용하면 $O(v)$만에 이 값을 구할 수 있다.

 

열심히 구현하면 된다!