고인물 복잡도

수식과 코드 넣는 법을 찾았다. 앞으로 깔끔한 포스팅을 위해 노력해야겠다.

 

 

$ F(n) = \sum_{i=1}^{n} \phi(n) $를 $ O(n^{2/3}) $에 구하는 방법이다.

수학적인 지식이 필요하지만 내용이 별로 어렵지 않다.

 

$ \phi(n) $의 정의 : $1$~$n$ 중 $n$과 서로소인 수의 개수

$ \phi(n) = x (1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})\cdots (1-\frac{1}{p_{k}}) $ (단, $ p_{1}, ..., p_{k} $는 $n$의 서로 다른 소인수들)

 

$F(n)$을 쉽게 계산하는 방법으로는 전부 계산해서 더해주는 방법이 있다. $\phi(n)$은 재귀적으로 빠른 시간 내에 계산해 줄 수 있어서 길게 잡아도 $O(n\log(n))$의 시간 안에 계산할 수 있다. 하지만 결국 모든 항을 계산 하면 아무리 빨라도 $O(n)$의 시간이 걸리기 때문에 충분하지 않다. 1부터 100까지의 합을 빠르게 계산하는 그런 비스무리한 방법이 필요한 것이다.

 

$Lemma.$ Following equation holds for $x \in \mathbb{Z}^{+} $
                 $x=\sum_{d | x} \phi(d)$
$Proof.$
$ \phi(n) = x (1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})\cdots (1-\frac{1}{p_{k}}) $
       $=x(1-(\frac{1}{p_{1}}+\cdots+\frac{1}{p_{n}})+(\frac{1}{p_{1}p_{2}}+\cdots)-\cdots)$
       $=x \sum_{d | x} \frac{\mu(d)}{d} $
       $=\sum_{d | x} \frac{\mu(x/d)}{d} $
라플라스 변환으로 성립
(별해. 1~x까지의 수를 x와의 gcd에 따라 나누어서 카운팅)

 

보조정리를 보면 대충 감이 온다. 여러개의 $\phi$함수의 합을 한번에 계산할 수 있는 방법이 생긴 것이다. 한발 더 가보자.

 

$Lemma.$ Let $F(n) = \sum_{i=1}^{n} \phi(i)$. Then following equation holds.
                 $F(n)=\frac{n(n+1)}{2}-\sum_{i=2}^{n} F(\lfloor\frac{n}{i}\rfloor)$
$Proof.$
$F(n) = \sum_{i=1}^{n} \phi(i)$
         $=\sum_{i=1}^{n}(i-\sum_{d | i, d\neq i} \phi(d) )$
         $=\sum_{i=1}^{n}i-\sum_{i=1}^{n}\sum_{d | i, d\neq i} \phi(d)$
         $=\sum_{i=1}^{n}i-\sum_{d=1}^{n}\sum_{d | i, d<i\leq n} \phi(d)$
         $=\sum_{i=1}^{n}i-\sum_{d=1}^{n}(\lfloor\frac{n}{d}\rfloor-1) \phi(d))$
         $=\sum_{i=1}^{n}i-\sum_{d=1}^{n}(\lfloor\frac{n}{d}\rfloor-1) (F(d)-F(d-1))$
         $=\sum_{i=1}^{n}i-\sum_{d=1}^{n-1}(\lfloor\frac{n}{d}\rfloor-\lfloor\frac{n}{d+1}\rfloor) F(d)$
         $=\frac{n(n+1)}{2}-\sum_{i=2}^{n} F(\lfloor\frac{n}{i}\rfloor)$

 

$\phi$함수 항 없이 오직 $F$로만 이루어진 점화식이 나왔다. 이제 dp를 통해 $F(n)$을 계산할 것이다.

일단 위의 점화식을 이용해 그냥 한번 계산해보자. $F(1)$ ~ $F(n)$을 전부 계산하는 것이다. 각 $F(i)$마다 $i$번의 연산이 걸리므로 총 $O(n^2)$의 시간이 걸리게 된다. 이제부터 여러 테크닉을 사용하여 시간 복잡도를 줄여볼 것이다.

 

테크닉 1) $\lfloor\frac{n}{i}\rfloor$로 가능한 값 $O(\sqrt{n})$개

$i$가 $1$~$\sqrt{n}$일 때 $\sqrt{n}$개, $i$가 $\sqrt{n}$보다 클 때 가능한 값이 $\sqrt{n}$이하이므로 또 $\sqrt{n}$개, 합쳐서 대충 $2\sqrt{n}$개이다. 이 사실을 이용하면 각 $F(i)$를 계산하는 시간을 줄여줄 수 있다. 가능한 값들 별로 몇번 등장하는지 $O(1)$시간에 연산해줄 수 있으므로 $O(n)$의 시간을 $O(\sqrt{n})$까지 줄여줄 수 있다.

여기까지 하면 전체시간은 $\sum_{i=1}^{n}\sqrt{i}$인 $O(n\sqrt{n})$의 시간이 걸리게 된다.

 

테크닉 2) $\lfloor\frac{\lfloor\frac{n}{x}\rfloor}{y}\rfloor=\lfloor\frac{n}{xy}\rfloor$

이 식이 무엇을 의미하냐면 $F(\lfloor\frac{n}{x}\rfloor)$을 점화식으로 계산하기 위해 필요한 항들은 $F(n)$을 계산 할 때도 필요한 항이라는 뜻이다. 즉, 점화식을 이용하여 dp를 할 때 $F(1)$~$F(n)$의 모든 항을 계산할 필요 없이 오직 $F(n)$을 계산할 때 필요한 항들만 계산해주면 된다는 뜻이다. 위 테크닉 1과 같은 이유로 $O(\sqrt{n})$개의 항만 계산하면 되고 마찬가지로 각 항을 계산하는데 $O(\sqrt{n})$의 시간만 사용하면 되므로 총 $O(n)$의 시간에 $F(n)$을 계산할 수 있게 된다.

 

테크닉 3) 전처리

step1 $F(1)$~$F(n^{\frac{2}{3}})$을 미리 계산. ($m=n^{\frac{2}{3}}$이라 정의)

$\phi(x)$는 $x$의 소인수 $p$ 하나를 알고 있으면 $\phi(\frac{x}{p})$을 통해 상수시간 내에 계산 할 수 있다.

$1$~$m$까지 모든 수의 소인수 하나 찾는 것은 $1$~$\sqrt{m}$들에 대해 각각의 배수들을 접근하면서 전처리해주면 되고 이는 $O(m\log m)$의 시간이 걸린다. (이 부분만 $O(m)$으로 줄이면 되는데 잘 모르겠다.)

$\phi(1)$~$\phi(m)$의 값들을 계산하면 $F(1)$~$F(m)$을 $O(m)$시간에 바로 구할 수 있으므로 $F(1)$~$F(m)$ 값들을 $O(m\log m)$의 시간에 전부 계산할 수 있는 것이다.

step2 남은 항들 계산.

$F(\lfloor\frac{n}{i}\rfloor)$에서 $i$가 $n^{\frac{1}{3}}$ 이하 일때만 계산해주면 된다.

각 항별로 $O(\sqrt{\frac{n}{i}})$의 시간이 걸리므로 전체 걸리는 시간은

$\sum_{i=1}^{n^{1/3}} \sqrt{\frac{n}{i}}=\int_{1}^{n^{1/3}} \sqrt{\frac{n}{i}}=\sqrt{n}\left[ \sqrt{i} \right]_{1}^{n^{1/3}}=O(n^{2/3})$

(이 부분 대충 각 항별로 $O(\sqrt{n})$ 걸린다하고 계산하면 $n^{5/6}$ 나온다. 엄밀히 해야한다.)

 

이렇게 최종적으로 $O(m)+O(m \log m)$의 시간에 $F(n)$을 계산할 수 있게 된다.

실제 문제 풀 때는 이런 귀찮은 과정이 필요없다. 대충 5백만까지 전처리.. 나머지는 점화식 뚝딱... 하면 해결된다.

문제 예시로 https://www.acmicpc.net/problem/16123 가 있다.

16123번: 피타고라스 쌍