식부터 세우자. $x$ 좌표의 차이가 $i$, $y$ 좌표의 차이가 $j$인 두 점 사이에 레이저를 쏘았다고 하자.
그러면 이때 드는 비용이 $A(\text{gcd}(i, j)+1) + B(i + j - 2 \text{gcd}(i, j))$임을 쉽게 유도할 수 있다.
즉, 구하고자 하는 값은 $\sum_{i=1}^n \sum_{j=1}^m 4(n+1-i)(m+1-j)((A-2B)\text{gcd}(i, j) + A + B(i+j))$다.
식을 정리하면, 결국 문제의 핵심 난이도는 $\sum_{i=1}^n \sum_{j=1}^m \text{gcd}(i, j)$를 계산하는 것이다.
여기서 $\text{gcd}(i, j)$ 대신 $i \text{gcd}(i, j)$, $j \text{gcd}(i, j)$, $ij \text{gcd}(i, j)$를 넣은 경우도 계산해야 한다.
전형적인 식 정리 방식을 사용한다. 먼저 $\text{gcd}(i, j)$로 예시를 보이고, 나머지는 결론만 제시한다.
$$\sum_{i=1}^n \sum_{j=1}^m \text{gcd}(i, j) = \sum_{g=1}^{\text{min}(n, m)} \sum_{i=1}^{n/g} \sum_{j=1}^{m/g} g [ \text{gcd}(i, j) = 1]$$
$$ = \sum_{g=1}^{\text{min}(n, m)} \sum_{i=1}^{n/g} \sum_{j=1}^{m/g} g \sum_{d|i, d|j} \mu(d) = \sum_{g=1}^{\text{min}(n, m)} \sum_{d=1}^{\text{min}(n,m)/g} g \cdot \mu(d) \sum_{i=1}^{n/gd} \sum_{j=1}^{m/gd} 1 $$
$$ = \sum_{T=1}^{\text{min}(n, m)} \left( \sum_{d|T} \mu(d) \cdot \frac{T}{d} \right) \cdot \lfloor \frac{n}{T} \rfloor \cdot \lfloor \frac{m}{T} \rfloor = \sum_{T=1}^{\text{min}(n, m)} \phi(T) \cdot \lfloor \frac{n}{T} \rfloor \cdot \lfloor \frac{m}{T} \rfloor$$
그러니 $\lfloor n/T \rfloor$, $\lfloor m/T \rfloor$가 가질 수 있는 구간의 개수가 적다는 점을 이용하여, 각 구간에 대한 $\phi$ 함수의 합을 차례대로 구해주면 충분하다. 이는 $f(x) = \phi(x)$, $g(x) = 1$, $(f * g)(x) = x$를 이용한 xudyh's sieve로 가능하다. 다른 식들도 마찬가지 방법으로 정리가 가능하고, 결국 $x \phi(x)$, $x^2 \phi(x)$의 부분합을 구하는 문제로 환원된다. 이들 역시 마찬가지 방법으로 xudyh's sieve를 사용하여 해결할 수 있다. 나름 전형적인 듯.
우선 집합의 크기부터 생각해보자. $2n$의 경우 $n+1$부터 $2n$을 뽑으면 $n$개를 확보한다.
$2n+1$의 경우 $n+1$부터 $2n+1$을 뽑으면 $n+1$개를 확보한다. 즉, "홀수의 개수"가 답이 됨을 알 수 있다.
특히, 모든 자연수는 홀수와 2의 거듭제곱의 곱으로 유일하게 표현이 가능하다.
만약 두 자연수가 위 표현에서 같은 홀수 부분을 가진다면, 두 자연수는 집합에 같이 속할 수 없다.
그러므로, 우리는 실제 최대 집합 크기가 "홀수의 개수"와 같음을 비둘기집의 원리로 증명한 셈이다.
이제 홀수들을 차례대로 나열하자. 우리는 각각에게 적합한 2의 거듭제곱을 줘서, 집합이 조건을 만족하도록 하고 싶다.
이때, 합을 최소로 하고 싶으므로, 가능한 최소의 2의 거듭제곱을 주고 싶다. 이를 그리디하게 하자.
만약 $n$이라는 홀수에 2를 주지 않았다면, $n/3$에는 무조건 2를 줘야 한다. 이런 느낌으로 가자.
결국 이를 정리하면 테스트 케이스 당 로그 시간이 걸리는 풀이가 나온다. 증명은 나도 잘 모르겟다 ㅋㅅㅋ
식을 정리하면, 우리가 구하고자 하는 답은 결국
$$ 3^n \cdot \sum_{0 \le a+b \le n} \frac{n!}{a! b! (n-a-b)!} \text{gcd}(a, b) = 3^n \cdot \sum_{g=1}^n \sum_{1 \le a+b \le n/g} \frac{n!}{(ga)! (gb)! (n-(ga+gb))!} \cdot g \cdot [ \text{gcd}(a, b) = 1] $$ $$ = 3^n \cdot \sum_{g=1}^n \sum_{1 \le a+b \le n/g} \frac{n!}{(ga)! (gb)! (n-(ga+gb))!} \cdot g \cdot \sum_{d|\text{gcd}(a, b)} \mu(d) $$ $$ = 3^n \sum_{g=1}^n \sum_{d=1}^{n/g} g \cdot \mu(d) \cdot \sum_{1 \le a+ b \le n/gd} \frac{n!}{(gda)!(gdb)!(n-(gda+gdb)!} $$ $$ = 3^n \cdot \sum_{T=1}^n \left( \sum_{d|T} \mu (d) \cdot \frac{T}{d} \right) \cdot \sum_{1 \le a+b \le n/T} \frac{n!}{(Ta)!(Tb)!(n-(Ta+Tb))!} $$ $$ = 3^n \cdot n! \cdot \sum_{T=1}^n \phi(T) \cdot \sum_{c=1}^{n/T} \frac{1}{(n-Tc)!} \cdot \sum_{a=0}^c \frac{1}{(Ta)!(T(c-a))!} $$
한편, 오른쪽 식의 형태는 convolution 형태를 띄고 있으므로, FFT를 이용하여 효율적으로 구할 수 있다.
모듈로가 일반적인 소수이므로, 루트로 쪼개는 트릭을 사용하여 계산하여야 한다. 이러면 끝.
우선 각 $m$에 대하여 답을 구한 다음 부분합을 취하면 되는 형태다. 아예 다 구하고 출력만 하라는 뜻이다.
또한, 각 $m$에 대한 답은 자명하게 (중국인의 나머지 정리) multiplicative 하다. 그러니 prime power에 대해서만 해결하자.
이 prime power가 홀수인 경우, 문제는 어렵지 않다. $(x+y)^2 \equiv a+2b$, $(x-y)^2 \equiv a-2b$이므로 $a+2b$, $a-2b$는 이차잉여이고, 역으로 이 조건만 만족하면 조건을 만족하는 $x, y$도 있기 때문이다. 그러므로 답은 해당 prime power에 대한 이차잉여의 개수를 제곱한 것이다.
prime power가 2의 거듭제곱인 경우 상황은 조금 복잡하다. 작은 거듭제곱의 경우 brute force로 답을 구할 수 있고, 믿음의 Berlekamp-Massey 알고리즘으로 답을 전처리할 수 있다. 아예 하드코딩해도 된다. 이제 이를 합쳐서 답을 구하는 것은 쉽다. 벌레캠프 각을 너무 늦게 봐서 해결이 오래 걸렸다.
BOJ 19000 Rikka with Proper Fractions
식을 또 열심히 정리해보자. 우리가 원하는 답은 결국
$$ \sum_{a/b \le c/d \le e/f, d \le n} [\text{gcd}(c, d) = 1] = \sum_{a/b \le c/d \le e/f, d \le n} \sum_{g| \text{gcd}(c, d)} \mu(g) $$ $$ = \sum_{g=1}^n \mu(g) \cdot \sum_{a/b \le c/d \le e/f, d \le n/g} 1 = \sum_{g=1}^n \mu(g) \cdot \sum_{d=1}^{n/g} \left( \lfloor \frac{e}{f}d \rfloor - \lfloor \frac{a}{b}d \rfloor + [ b|ad] \right)$$
이제 $\lfloor n/g \rfloor$로 가능한 값이 적으므로 xudyh's sieve로 $\mu$의 부분합을 빠르게 구하면 된다.
또한, $\sum_{k=1}^n \lfloor ak/b \rfloor$ 형식의 값을 빠르게 구해야 하는데, 이는 이 문제와 같다.
진짜 개고생을 해서 풀었기 때문에, 풀이를 간단하게 스케치만 남긴다. 생각의 과정만 담는 수준으로 적는다.
- 우선 $k$가 작다는 것이 핵심인 것으로 보인다. $n$ 자체는 문제 풀이에 영향이 거의 없어야 한다.
- 사실 $x(x+1) \cdots (x+k)$를 더하는 문제면 엄청나게 간단한 문제가 된다. $\text{lcm}$이 붙어서 문제다.
- 그러면 $x(x+1) \cdots (x+k) / \text{lcm}(x, x+1, \cdots, x+k)$를 생각해보자.
- 생각해보면, 이 값이 가질 수 있는 소인수는 전부 30 이하이다.
- 또한, 이 값이 $2$를 얼마나 갖는지는 $x \pmod{32}$에 의해서만 결정된다. $3$의 경우 $\pmod{27}$이고 등등.
- 중국인의 나머지 정리로, 대략 $x \pmod{N}$에 의해서만 저 값이 결정된다. $N$은 대략 $10^{12}$ 스케일의 값.
- 이걸 전부 나열하면 $\mathcal{O}(Nk)$ 수준의 풀이가 나온다. 저 $N$이 문제인데, 약간 meet-in-the-middle 같다.
- 소인수를 두 그룹으로 나누고, 양쪽을 "잘 합치는" 방법을 생각해야 한다.
- 이게 생각보다 어려운데, 커팅도 많이 하고 알고리즘 자체도 생각해야 하고 수학도 많이해야 한다.
'PS > 수학 계열 PS' 카테고리의 다른 글
| 8월의 PS 일지 - Part 5 (0) | 2020.08.12 |
|---|---|
| 8월의 PS 일지 - Part 3 (0) | 2020.08.10 |
| Brief Introduction to Hackenbush Games (1) | 2020.05.17 |
| 5월의 PS 일지 - Part 1 (0) | 2020.05.16 |
| 4월의 PS 일지 - Part 5 (0) | 2020.05.02 |