BOJ #16164 Möbius Madness

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

문제

주어지는 양의 정수 \(N, L, K\)에 대하여, 다음 값을 \(10^9 + 7\)로 나눈 나머지를 구하시오. $$ \sum_{d=1}^N \mu (L \cdot d) \left \lfloor \frac{N}{d} \right \rfloor^K $$ 단, \(1 \le N \le 10^9\), \(1 \le L \le 10^{15}\), \(1 \le K \le 10^9\)이며, 시간 제한은 2.5초이다. 

스포 방지선

________________________________________________________________________________________________________________________

________________________________________________________________________________________________________________________

풀이

우선 여기에 설명되어 있는 테크닉인 xudyh's sieve에 대한 이해가 필요하다. 

두 multiplicative function \(f(x)\)와 \(g(x)\)가 다음을 만족한다고 하자.

• \(g(x)\)의 partial sum, 즉 \(\sum_{i=1}^n g(i)\)를 빠른 시간에 구할 수 있다. 
• \((f * g)(x)\)의 partial sum, 즉 \(\sum_{i=1}^n (f*g)(i)\)를 빠른 시간에 구할 수 있다.
• 단, 여기서 \((f*g)(x)\)는 \(f(x)\)와 \(g(x)\)의 Dirichlet Convolution이다. 
• 여기서 빠른 시간은 상수 시간이나 로그 시간, 로그 제곱 시간 정도를 말한다.

그러면, 각 \(1 \le k \le n\)에 대해 \(\sum_{i=1}^{\lfloor n/k \rfloor} f(i)\)를 \(\mathcal{O}(n^{2/3})\) 정도 시간에 구할 수 있다. 

여기서 가능한 \(\lfloor \frac{n}{k} \rfloor\)의 값의 종류가 \(\mathcal{O}(\sqrt n)\)개임을 참고하자. 자세한 방법론과 구현 방법은 링크 참조. 

문제를 풀기 위해서, 먼저 \( \left \lfloor \frac{N}{d} \right \rfloor ^K\)라는 항부터 보자. \( \left \lfloor \frac{N}{d} \right \rfloor \)로 가능한 값의 종류가 \(\mathcal{O}(\sqrt N)\)개이므로, 그 값에 따라서 \(d\)를 \(\mathcal{O}(\sqrt N)\)개의 구간으로 묶어줄 수 있다. 예를 들어, \(lef_v \le d \le rig_v \iff \left \lfloor \frac{N}{d} \right \rfloor = v\)라고 하면, \(lef_v \le d \le rig_v\)에 대하여 \( \left \lfloor \frac{N}{d} \right \rfloor^K\)라는 값은 \(v^K\)로 일정하므로, \( \sum_{d=lef_v}^{rig_v} \mu(L \cdot d)\)를 구해주면 된다. 

또한, 모든 \(\left \lfloor \frac{N}{d} \right \rfloor\) 형태로 쓸 수 있는 자연수 \(v\)에 대하여, \(rig_v = \left \lfloor \frac{N}{v} \right \rfloor \)임을 쉽게 확인할 수 있다. 

그러므로 모든 \(\left \lfloor \frac{N}{d} \right \rfloor\) 형태로 쓸 수 있는 자연수 \(v\)에 대하여, \(rig_v\)와 \(lef_v-1\)은 모두  \(\left \lfloor \frac{N}{d} \right \rfloor\) 형태로 쓸 수 있다.

결국 남은 것은 각 \(1 \le k \le n\)에 대해 \(\sum_{d=1}^{\lfloor N/k \rfloor} \mu(L \cdot d) \)를 빠르게 구하는 것이다. 

우선 \(L\)이 square-free하지 않다면, \(\mu(L\cdot d)\)는 \(d\)와 관계 없이 무조건 \(0\)일 것이다. 

그렇지 않다면, \(\mu_L(d) = \frac{\mu (L \cdot d)}{\mu (L)}\)이라 하자. 이제 목표를 다시 쓰자. 

우리의 목표는 각 \(1 \le k \le n\)에 대해 \(\sum_{d=1}^{\lfloor N/k \rfloor} \mu_L(d) \)를 빠르게 구하는 것이다. 

 

Claim: \(\mu_L(x)\)는 multiplicative function이다. 

Proof of Claim: \(\text{gcd}(d,L) \neq 1\)이라면 \(\mu_L(d)=0\)이고, \(\text{gcd}(d,L)=1\)이면 \(\mu_L(d) = \mu(d)\)이다. 

이제 xudyh's sieve를 쓸 각을 재보자. \(g(x)=1\)을 선택한다. 이제 \( (\mu_L * g) (x)\)에 대해 생각해보자. 

\(p|L\)인 소수 \(p\)와 자연수 \(k\)에 대해, \((\mu_L * g)(p^k) = \sum_{i=0}^k \mu_L(p^i) = 1\)이다.

\(L\)의 약수가 아닌 소수 \(q\)와 자연수 \(k\)에 대해, \((\mu_L * g)(q^k) = \sum_{i=0}^k \mu_L(q^i) = 0\)이다.

\((\mu_L * g)(x)\)도 multiplicative function이니, 우리는 다음과 같은 결론을 얻을 수 있다. 

모든 소수 \(p\)에 대해 \(p|x \implies p|L\)이 성립하면, \((\mu_L * g)(x) = 1\)이고, 그렇지 않다면 \((\mu_L * g)(x)=0\)이다. 

결국 \(\sum_{i=1}^n (\mu_L * g)(i)\)는 \([1, n]\)에 속한 자연수 중 \(L\)의 소인수들로만 구성된 자연수의 개수이다. 

\(L\)의 소인수들로만 구성된 자연수는 생각보다 많지 않다. \(L \le 10^{15}\)이므로, \(L\)이 가질 수 있는 소인수의 개수도 적다. \([1,N]\)에 속한 자연수 중 \(L\)의 소인수들로만 구성된 자연수는 priority_queue 등을 통하여 모두 구할 수 있다. 

이제 \(\sum_{i=1}^n (\mu_L * g)(i)\)는 lower_bound 등의 함수를 통해 빠르게 구할 수 있다. 

결국 xudyh's sieve를 쓰기 위한 필요 조건이 모두 갖추어졌고, 구현만 하면 된다. 끝.