루미의 생일파티장 꾸미기 (EX)

• 이 문제는 $N$이 커서 $\varphi(1), \ldots, \varphi(N)$을 배열에 담을 수 없습니다. 그래서 $\sum_{x=1}^{N} \varphi(xL)$을 다른 식으로 바꿉니다.
• $L$을 소인수분해한 결과를 $L = p_1^{e_1} \cdots p_k^{e_k}$라 하고, 라 합시다.
• $\mathbb{P}(x)$는 $x$의 소인수 집합입니다. $\mathbb{P}(1) = \emptyset$입니다.
• 예를 들어, $\mathbb{P}(12) = \{2, 3\}$입니다.

Claim

$$\sum_{x=1}^{N} \varphi(xL) = \varphi(L) \sum_{\mathbb{P}(d) \subseteq \mathbb{P}(L)} \sum_{x=1}^{\left\lfloor \frac{N}{d} \right\rfloor} \varphi(x)$$

• $\mathbb{P}(d) \subseteq \mathbb{P}(L)$은 $d$가 $L$의 소인수만으로 이루어진 수라는 뜻입니다.
• 예를 들어 $L = 12$이면 이 조건을 만족하는 는 등이 있습니다.

증명

• $\varphi(xL) = p_1^{e_1 - 1} \cdots p_k^{e_k - 1} \varphi(x p_1 \cdots p_k)$입니다.

$k = 1$일 때 $L = p$라 하면

$$\begin{array}{rl}{\displaystyle \sum _{x=1}^N\phi (xp)}& {\displaystyle =\sum _{\begin{array}{c}p\mid x\\ x\le N\end{array}}\phi (xp)+\sum _{\begin{array}{c}p\nmid x\\ x\le N\end{array}}\phi (xp)}\\ {\displaystyle }& {\displaystyle =\sum _{\begin{array}{c}p\mid x\\ x\le N\end{array}}p\phi (x)+\sum _{\begin{array}{}\end{array}}}\end{array}$$

입니다. 같은 전개를 반복하면 $\sum_{x=1}^{N} \varphi(xp) = \varphi(p) \sum_{j \ge 0} \Phi\left(\left\lfloor \frac{N}{p^j} \right\rfloor\right)$이고, 인 는 뿐이므로 일 때 Claim이 성립합니다.

• 소인수가 $k$개인 $L = p_1 \cdots p_k$에서 Claim이 성립한다고 가정하고, $L^{\mathrm{\prime }}=$이라 합시다.

$$\begin{array}{rl}{\displaystyle \sum _{x=1}^N\phi (x{L}^{\mathrm{\prime }})}& {\displaystyle =\sum _{\begin{array}{c}{p}_{k+1}\mid x\\ x\le N\end{array}}\phi (x{L}^{\mathrm{\prime }})+\sum _{\begin{array}{c}{p}_{k+1}\nmid x\\ x\le N\end{array}}\phi (x{L}^{\mathrm{\prime }})}\\ {\displaystyle }& {\displaystyle =\sum _{\begin{array}{c}{p}_k\end{array}}}\end{array}$$

• 같은 전개를 반복하고, 각 합에 가정을 적용합니다. $\left\lfloor \left\lfloor N/a \right\rfloor / b \right\rfloor = \left\lfloor N/(ab) \right\rfloor$를 쓰면

$$\begin{array}{rl}{\displaystyle \sum _{x=1}^N\phi (x{L}^{\mathrm{\prime }})}& {\displaystyle =\phi (p_{k+1})\sum _{j\ge 0}\sum _{x=1}^{\lfloor N\mathrm{/}{p}_{k+1}^j\rfloor }\phi (xL)}\\ {\displaystyle }& {\displaystyle =\phi (p_{k+1})\phi (L)\sum _{j\ge 0}\sum _{\mathbb{P}(d)\subseteq \mathbb{P}(L)}\mathrm{\Phi }(\lfloor \frac{N}{p_{k+}^{}}}\end{array}$$

• $\varphi(p_{k+1})\,\varphi(L) = \varphi(L')$이고, $$는 인 수를 한 번씩 모두 지납니다. 따라서 일 때도 Claim이 성립합니다.

계산

• 이제 $\mathbb{P}(d) \subseteq \mathbb{P}(L)$인 $d$를 모두 구하고, 각 $d$에 대해 $\Phi\left(\left\lfloor \frac{N}{d} \right\rfloor\right)$를 구해 더한 뒤 을 곱하면 됩니다.