9월초 수학 PS 일지

8문제. 대략 난이도순.

BOJ 17257 불확정성이 넘쳐흘러

무난한 문제. \(f_Y(i,j)\)의 값은 구간의 길이인 \(j-i+1\)에만 영향을 받는다. 

또한, 한 구간의 gcd가 1인 것은 구간에 속한 모든 자연수가 \(p\)의 배수가 되는 소수 \(p|Y\)가 존재하지 않는 것과 동치이다. 

한편, 배열에 들어갈 수 있는 값은 \([1,Y]\) 중 하나이므로, 각 소수를 독립적으로 생각할 수 있다.

여기까지 관찰하면 남는 것은 정말 간단한 단순 계산 문제. 대충 \(\mathcal{O}(N \log NY + \sqrt{Y})\) 정도에 풀린다.

BOJ 16998 It's a Mod, Mod, Mod World

이러한 문제들은 대부분 유클리드 호제법과 비슷한 느낌으로 풀리는 경우가 많다. 

문제를 주어진 \((p,q)\)에 대해 \(\sum_{i=1}^n \lfloor \frac{pi}{q} \rfloor\)를 계산하는 문제로 변환하자.

쉽게 관찰할 수 있는 것은, \((p,q)\)에 대한 문제는 \((p\text{%}q, q)\)에 대한 문제로 간단하게 변환이 가능하다는 것이다.

우리가 \((p,q)\)에 대한 문제를 빠르게 \((q,p)\)에 대한 문제로 변환할 수 있다면, 유클리드 호제법 과정을 그대로 거쳐서 로그 시간에 문제를 해결할 수 있을 것이다. (분모, 분자가 \(10^{18}\) scale인 분수를 double, int128 없이 비교하는 방식도 비슷하다)

이를 위한 대표적인 방법은 문제를 좌표평면에 \(y = \frac{p}{q}x\)를 그리고, \(1 \le x \le n\), \(1 \le y \le \frac{p}{q}x\)를 만족하는 정수점의 개수를 세는 문제로 변환하는 것이다. 이제 역으로 \( x = \frac{q}{p}y\)를 생각하고, \(1 \le y \le \lfloor \frac{pn}{q} \rfloor \), \( 1 \le x \le \frac{q}{p}y\)인 점들을 생각하자. 

두 그룹의 모두 속하는 정점은 \(y = \frac{p}{q}x\) 위에 놓이는 점들로, 이들의 개수는 쉽게 계산된다. 

이 관찰을 모두 하면 \((p,q)\)에서 \((q,p)\)로 문제를 전환하는 것은 어렵지 않다. 여기서부터는 단순 계산.

BOJ 11691 LCM(i, j)

\(\displaystyle \sum_{1 \le u < v \le n} \frac{uv}{\text{gcd}(u,v)} \)를 계산해야 한다. \(g=\text{gcd}(u,v)\)를 고정하자.

그러면 식은 \(\displaystyle \sum_{g=1}^n \sum_{1 \le u' < v' \le \lfloor \frac{n}{g} \rfloor, \text{gcd}(u',v')=1} gu'v'\)이다.  \(\displaystyle F(x) = \sum_{1 \le u' < v' \le x, \text{gcd}(u',v')=1} u'v' \)이라 하자.

\(v'\)을 고정하면서 생각하면 \(\displaystyle F(x) = \sum_{i=2}^x \frac{i^2 \phi(i)}{2}\)임을 알 수 있다. 남은 것은 \(\phi(i)\)들을 전처리하고 단순 계산을 하는 것 뿐.

물론, 여기까지 관찰하면 xudyh's sieve를 끼얹어서 문제를 \(\mathcal{O}(n^{2/3})\)에 풀 수 있다. 

BOJ 4862 마지막 자리

BOJ 13358, BOJ 12445, BOJ 12446, BOJ 16214 등 power tower를 다루는 모든 문제에서 사용되는 정리가 필요하다.

예전 블로그에 그 정리에 대한 설명을 써놓았기 때문에, 링크를 걸어놓는 것으로 설명을 대체한다. 마지막 문제다.

BOJ 8293 Prime Prime Power

자연수가 prime prime power이면, prime prime power로의 표현 방법은 유일하다. 

또한, 지수가 3 이상인 prime prime power는 모두 직접 구할 수 있을 정도로 적으니, 모두 구해놓자.

문제는 지수가 2인 prime prime power이다. 여기서 아이디어는 prime gap이 작다는 것을 이용하는 것이다.

\(n \le 10^9\)이면, \(n\)과 \(n+3 \cdot 10^6\) 사이에는 \(100000\)개 이상의 소수가 있다는 믿음을 가지자.

이러면 남은 문제는 쉽다. \(\lfloor \sqrt{n} \rfloor\)부터 \(\lfloor \sqrt{n} \rfloor + 3 \cdot 10^6\) 사이에 존재하는 수들이 소수인지를 빠르게 확인한다. 

에라토스테네스의 체를 응용하면 어렵지 않게 할 수 있다. 이제 이분탐색을 끼얹으면 빠른 시간안에 문제를 해결할 수 있다. 

BOJ 14861 LCM 더하기

먼저 \(x \in [1, n]\), \(y \in [1, m]\)인 \((x,y)\)에 대해서 \(\text{lcm}(x,y)\)를 다 더한 값을 빠르게 구하는 방법을 생각해보자.

명제 \(P\)에 대해서 \([P]\)를 \(P\)가 참이면 1, 아니면 0인 값으로 정의하도록 하자. 

\(\text{gcd}(x,y)=g\)를 고정하면, 계산해야 하는 식은 \(\displaystyle \sum_{g=1}^{\text{min}(n,m)} \sum_{x=1}^{\lfloor \frac{n}{g} \rfloor} \sum_{y=1}^{\lfloor \frac{m}{g} \rfloor} gxy \cdot [\text{gcd}(x,y) =1] \)이다. 

그런데 \([n=1] = \sum_{d|n} \mu(d)\)임은 정수론 문제에서 아주 자주 쓰이는 식이다. 이를 사용하면, $$ \sum_{g=1}^{\text{min}(n,m)} \sum_{x=1}^{\lfloor \frac{n}{g} \rfloor} \sum_{y=1}^{\lfloor \frac{m}{g} \rfloor} gxy \cdot \sum_{d|\text{gcd}(x,y)} \mu(d) $$를 계산하면 충분함을 파악할 수 있다. 식을 \(d\)에 대해서 다시 쓰면 주어진 식은 $$ \sum_{d=1}^{\text{min}(n,m)} \mu(d) \cdot \sum_{g=1}^{\text{min}(n,m)} g \cdot \left( \sum_{x=1}^{\lfloor \frac{n}{gd} \rfloor} d \cdot x \right) \cdot \left( \sum_{y=1}^{\lfloor \frac{m}{gd} \rfloor} d \cdot y \right) = \sum_{d=1}^{\text{min}(n,m)} \mu(d) \cdot \sum_{g=1}^{\text{min}(n,m)} g \cdot \frac{d^2 \cdot \lfloor \frac{n}{gd} \rfloor \left( \lfloor \frac{n}{gd} \rfloor + 1 \right) \cdot \lfloor \frac{m}{gd} \rfloor \left( \lfloor \frac{m}{gd} \rfloor + 1 \right)}{4} $$로 변환된다. 여기서 \(k=gd\)라고 두고, \(k\)에 대해서 식을 정리하면, 주어진 식은 다시 $$ \sum_{k=1}^{\text{min}(n,m)} \frac{\lfloor \frac{n}{k} \rfloor \left(\lfloor \frac{n}{k} \rfloor + 1 \right) \cdot \lfloor \frac{m}{k} \rfloor \left( \lfloor \frac{m}{k} \rfloor + 1 \right)}{4} \cdot \left( \sum_{d|k} k \cdot d \cdot \mu(d) \right) $$와 같음을 알 수 있다. \(f(k) = \sum_{d|k} d \cdot \mu(d)\)라 하면, 간단하게 식을 정리해 $$ \sum_{k=1}^{\text{min}(n,m)} \frac{\lfloor \frac{n}{k} \rfloor \left(\lfloor \frac{n}{k} \rfloor + 1 \right) \cdot \lfloor \frac{m}{k} \rfloor \left( \lfloor \frac{m}{k} \rfloor + 1 \right)}{4} \cdot kf(k)$$를 얻을 수 있다. 이제 준비가 끝났다. \(\lfloor \frac{n}{k} \rfloor\)가 가질 수 있는 값의 개수는 \(\mathcal{O}(\sqrt{n})\)이다. 

그러므로 \(f(k)\)를 먼저 모두 계산한 뒤, \(kf(k)\)의 부분합을 전처리하면 위 식을 \(\mathcal{O}(\sqrt{n}+\sqrt{m})\)에 계산할 수 있다.

이제 \(\text{gcd}(x,y)\)가 squarefree한 경우만을 계산하는 방법을 고민하자. \(g(n,m)\)을 \(\sum_{x=1}^n \sum_{y=1}^m \text{lcm}(x,y)\)라고 하자. 

포함-배제의 원리에서, 우리가 구해야 하는 것은 \(\displaystyle \sum_{t=1}^{\sqrt{\text{min}(n,m)}} \mu(t) \cdot t^2 \cdot g\left(\left\lfloor \frac{n}{t^2} \right\rfloor, \left\lfloor \frac{m}{t^2} \right\rfloor\right)\)이다.

\(g(n,m)\)을 \(\mathcal{O}(\sqrt{n}+\sqrt{m})\) 시간에 구할 수 있으니, 저 식도 대략 \(\mathcal{O}((\sqrt{n}+\sqrt{m}) \log \text{min}(n,m))\)에 구할 수 있다.

전처리 과정이 필요한 부분은 \(f(k)\) 값들과 \(\mu\) 값들이 전부이며, 모두 간단하게 전처리할 수 있다.

전체 시간복잡도는 대략 \(\mathcal{O}(MAX \log MAX + TC \sqrt{MAX} \log MAX)\)이다. 

BOJ 16941번 꼬리별

결국에는 \(\displaystyle \sum_{p \le P, p \in \text{prime}} p^Q\)를 빠르게 계산하는 문제이다. 개인적으로 아직 공부가 덜 된 유형이다 ㅠㅠㅠ

기본적으로 sum of powers를, 즉 \(1^Q+2^Q+ \cdots + N^Q\)를 빠르게 구하는 과정이 필요하다.

개인적으로는 베르누이 수를 많이 사용하는데, 문제는 베르누이 수가 유리수라서 \(\pmod P\) 연산을 하기가 까다롭다.

실제로는 \(Q \le 1000\)이므로, \(P > 5000\)이면 사용하는 베르누이 수들의 분모에 \(P\)가 없게 되어 문제가 없다. 

그러니까 \(P<5000\)이면 naive하게 처리하고, \(P > 5000\)인 경우를 보도록 하자.

베르누이 수를 전처리하면, \(N\)이 주어졌을 때 \(1^Q+2^Q+ \cdots +N^Q\)를 \(\mathcal{O}(Q)\)에 구할 수 있다. 참고

에라토스테네스의 체에서 숫자들을 지워가는 과정을 모방하는 방식으로 문제에 접근할 수 있다.

현재 에라토스테네스의 체에서 현재 소수 \(r\)을 보고 있다고 하자. 

아직 지워지지 않은 수들은 \(r\) 미만의 소수이거나, 아니면 최소 소인수가 \(r\) 이상인 수들이다. 

이제 \(r\)이 아닌 \(r\)의 배수들을 모두 지운다. 새롭게 지워지는 수들은 어떤 형태를 가지고 있을까?

새롭게 지워지는 수들은 \(r \cdot k\) 형태의 수로, \(k\)는 역시 최소 소인수가 \(r\) 이상인 수이다. 

즉, \(r \cdot k\)가 새롭게 지워지는 것은 [\(k\)가 아직 지워지지 않았고, \(r\) 미만의 소수가 아님]과 동치이다.

 \(dp_N\)을 \(N\) 이하의 수 중 아직 지워지지 않은 수들의 \(Q\)제곱의 합이라고 하자.

위 과정을 잘 생각해보면, \(dp_{\lfloor \frac{P}{i} \rfloor}\) 형태의 \(dp\) 값들만 생각해도 모든 계산이 가능함을 알 수 있다. 

물론, \(\lfloor \frac{P}{i} \rfloor\)로 가능한 수의 개수는 \(\mathcal{O}(\sqrt{P})\)이다. \(dp_k\)의 초깃값을 \(2^Q+3^Q+ \cdots +k^Q\)로 초기화한 후, 위에서 언급한 접근을 활용하여 \(dp\)의 값들을 변경해주자. 잘 구현하면, \(\mathcal{O}(P^{3/4} \log Q + \sqrt{P}Q+Q^2)\) 정도로 문제가 풀린다.

굉장히 많은 부분을 (코드 포함) 이 글에서 배웠다. 코드도 사실 저 글에서 거의 복붙한 수준이다.

pps789님의 코드가 굉장히 잘 이해되고 굉장히 빨라서, 그 코드를 사용해서 이 내용을 다시 공부할 생각이다.

BOJ 13714번 약수의 개수

핵심 아이디어는 구하고자 하는 식이 \(\displaystyle \sum_{(i,j)=(j,k)=(k,i)=1} \lfloor \frac{a}{i} \rfloor \cdot \lfloor \frac{b}{j} \rfloor \cdot \lfloor \frac{c}{k} \rfloor\)로 변형된다는 사실이다.

앞에서 정의한 것처럼, 명제 \(P\)에 대해서 \([P]\)를 \(P\)가 참이면 1, 아니면 0으로 정의하자.

이제 문제는 굉장히 간단해진다. 먼저 각 \(1 \le N \le ab\)에 대해서 \(\sum_{i=1}^c \lfloor \frac{c}{i} \rfloor \cdot [\text{gcd}(i,N)=1]\)을 전처리하자. 

이 식은 \(\displaystyle \sum_{i=1}^c \lfloor \frac{c}{i} \rfloor \cdot \sum_{d|\text{gcd}(i,N)} \mu(d) = \sum_{d|N} \mu(d) \sum_{i=1}^{\lfloor \frac{c}{d} \rfloor} \lfloor \frac{c}{di} \rfloor\)으로, \(\mu\) 함수를 전처리한 뒤 쉽게 계산할 수 있다.

전처리한 이 식을 \(f(N)\)이라 하자. 구해야 하는 값은 \(\displaystyle \sum_{i=1}^a \sum_{j=1}^b [\text{gcd}(i,j)=1] \cdot \lfloor \frac{a}{i} \rfloor \cdot \lfloor \frac{b}{j} \rfloor \cdot f(i \cdot j)\)다.

\(f\)가 전처리가 되었다면, 이 식은 그냥 naive하게 구할 수 있다. 단순 계산. 

이제 우리가 구하고자 하는 식이 \(\displaystyle \sum_{(i,j)=(j,k)=(k,i)=1} \lfloor \frac{a}{i} \rfloor \cdot \lfloor \frac{b}{j} \rfloor \cdot \lfloor \frac{c}{k} \rfloor\)과 같음을 증명하자.

\(\displaystyle f(a,b,c)=\sum_{i=1}^a \sum_{j=1}^b \sum_{k=1}^c \tau(i \cdot j \cdot k)\)라 하고, \(\displaystyle g(a,b,c)=\sum_{(i,j)=(j,k)=(k,i)=1} \lfloor \frac{a}{i} \rfloor \cdot \lfloor \frac{b}{j} \rfloor \cdot \lfloor \frac{c}{k} \rfloor\)라 하자.

\(f(a,b,c)=g(a,b,c)\)임을 \(a+b+c\)에 대한 강한 귀납법으로 증명한다. Base Case는 생략한다. 우리는 두 식

\(f(a,b,c)-f(a-1,b,c)-f(a,b-1,c)-f(a,b,c-1)+f(a,b-1,c-1)+f(a-1,b,c-1)+f(a-1,b-1,c)-f(a-1,b-1,c-1)\)

\(g(a,b,c)-g(a-1,b,c)-g(a,b-1,c)-g(a,b,c-1)+g(a,b-1,c-1)+g(a-1,b,c-1)+g(a-1,b-1,c)-g(a-1,b-1,c-1)\)이 같음을 보이면 충분하다. 물론, 첫 번째 식은 단순하게 \(\tau(abc)\)와 같다. 

두 번째 식은 \(\displaystyle \sum_{(i,j)=(j,k)=(k,j)=1} \left( \lfloor \frac{a}{i} \rfloor - \lfloor \frac{a-1}{i} \rfloor \right) \left( \lfloor \frac{b}{j} \rfloor - \lfloor \frac{b-1}{j} \rfloor \right) \left(\lfloor \frac{c}{k} \rfloor - \lfloor \frac{c-1}{k} \rfloor \right)\)이다.

그런데 자연수 \(n, k\)에 대해서 \(\lfloor \frac{n}{k} \rfloor - \lfloor \frac{n-1}{k} \rfloor\)은 \(n\)이 \(k\)의 배수일 때만 \(1\)이고 나머지 경우에는 \(0\)이다.

즉, 두 번째 식은 \((i,j)=(j,k)=(k,i)=1\)이고 \(i,j,k\)가 각각 \(a,b,c\)의 약수인 경우의 수와 같다.

첫 번째 식과 두 번째 식의 의미를 생각해보면, 결국 각 소인수에 대해서 독립적으로 생각해도 됨을 알 수 있다.

소수 \(p\)를 고정하자. \(a, b, c\)가 각각 \(p\)를 \(u, v, w\)개 가진다고 하자. 물론 \(u, v, w \ge 0\)이다.

첫 번째 식에서 소수 \(p\)에 의해 곱해지는 값은 \(abc\)가 \(p\)를 \(u+v+w\)개 가지므로 \(u+v+w+1\)과 같다. 

두 번째 식에서 소수 \(p\)에 의해 곱해지는 값도 \(u+v+w+1\)과 같다. \(0 \le i' \le u\), \(0 \le j' \le v\), \(0 \le k' \le w\)인 \(i',j',k'\)를 고르되, (물론, 이 값들은 \(i,j,k\)가 갖는 \(p\)의 개수가 된다) \(i', j', k'\) 중 최대 하나가 양수인 경우의 수를 세면 정확히 \(u+v+w+1\)이기 때문이다. 결국 첫 번째 식과 두 번째 식은 정확히 같다. 증명 끝. 남은 것은 크게 복잡하지는 않은 구현.