[BOJ 16164] Möbius Madness
https://www.acmicpc.net/problem/16164
Task
Compute:
\[ \sum_{d=1}^{N} \mu(Ld) \left\lfloor \frac{N}{d} \right\rfloor^{K} \]
for given integers $N$, $K$, and $L$.
Solution
First, we observe that if $\mu(L) = 0$, the entire sum becomes zero. Thus, we only need to consider the case where $\mu(L) \neq 0$. In this case, we can factor out $\mu(L)$ from the sum:
\[ \mu(L) \sum_{d=1}^{N} \frac{\mu(Ld)}{\mu(L)} \left\lfloor \frac{N}{d} \right\rfloor^{K} \]
Let’s denote as:
\[ \mu_L(d) = \frac{\mu(Ld)}{\mu(L)} = \mu(d) [ \gcd(d, L) = 1 ] \]
Then, our task reduces to computing:
\[ \mu(L) \sum_{i:d_i \le N} \left( S_{\mu_L}(d_{i+1}-1) - S_{\mu_L}(d_i - 1) \right) a_i^{K} \]
where $d_0 = 1$, $a_i = \left\lfloor \frac{N}{d_i} \right\rfloor$, and $d_{i+1} = \left\lfloor \frac{N}{a_i} \right\rfloor + 1$. To compute this efficiently, we need to find a way to compute $S_{\mu_L}(n) = \sum_{i=1}^{n} \mu_L(i)$ quickly. Let’s use the Mertens trick. We can verify that $\mu_L(d)$ is a multiplicative function. Specifically, for a prime $p$:
- If $p | L$, then $\mu_L(p) = 0$.
- If $p \nmid L$, then $\mu_L(p) = -1$
- $\mu_L(1) = 1$
- $\mu_L(p^k) = 0$ for $k \ge 2$.
Remining that $\mu_L * 1$ is also multiplicative, we have:
\[ (\mu_L * 1)(n) = \prod_{p^k | n} (1 + \mu_L(p)) \]
Let’s denote $P(n) = \Set{p \in \mathbb{P} | p | n}$. Then, we can express $(\mu_L * 1)(n)$ as:
\[ (\mu_L * 1)(n) = [ P(n) \subseteq P(L) ] \]
Thus, the recursion for $S_{\mu_L}(n)$ becomes:
\[ \begin{align*} S_{\mu_L}(n) &= \frac{1}{1(1)} \left( S_{\mu_L * 1}(n) - \sum_{i:2\le d_i \le n} S_{\mu_L}(a_i) \left( S_1(d_{i+1}-1) - S_1(d_i-1) \right) \right) \nl &= S_{\mu_L * 1}(n) - \sum_{i:2\le d_i \le n} S_{\mu_L}(a_i) \left( d_{i+1}-d_i \right) \end{align*} \]
We need to compute $S_{\mu_L * 1}(n)$ efficiently.
\[ S_{\mu_L * 1}(n) = \sum_{i=1}^{n} [ P(i) \subseteq P(L) ] \]
which counts the integers up to $n$ whose prime factors are all in $P(L)$. We can compute this using a depth-first search (DFS) approach. Starting from 1, we can multiply by each prime in $P(L)$ and generate all valid integers up to $n$.
\[ V = \Set{ n \le N | P(n) \subseteq P(L) } \]
After generating these integers, counting integers less than or equal to $n$ can be done using binary search. Here, we can estimate as $|V| = O\left((\log N)^{c}\right)$ for some small constant $c$. Computing $S_{\mu_L * 1}$ at each step takes $O(\log |V|) = O(\log \log N)$ time due to binary search. Precomputing $S_{\mu_L}(n)$ up to $M$ takes $O(M \log \log M)$ time. Thus, the overall time complexity for computing $S_{\mu_L}(N)$ becomes:
\[ O\left( M \log \log M + \frac{2N}{\sqrt{M}} + \frac{N}{M} \log \log N \right) \]
Choosing $M \approx N^{2/3}$ balances the terms, leading to an optimized complexity of:
\[ O\left( N^{2/3} \log \log N \right) \]
Factorizing $L$ requires $O(L^{1/4})$ time using Pollard’s rho algorithm. Conducting the DFS takes $O(|V| \cdot |P(L)|) < O\left((\log N)^{c} \log L\right)$ time. Calculating the final sum takes $O(\sqrt{N} \log K)$ time. Thus, the overall time complexity is:
\[ O\left( N^{2/3} \log \log N + L^{1/4} + (\log N)^c \log L + \sqrt{N} \log K \right) \]
which is efficient enough for the given constraints.
