8월의 PS 일지 - Part 3

추가적으로 더 해결한 수학 문제들과, 최근에 친 AGC 문제들을 다룬다.

BOJ 15983 순간이동 발판

두 발판 사이로 이동할 수 있는 시각은 $A \pmod{B}$ 형태의 값을 갖는 자연수들이 된다.

각 위치에 대해서 "그 위치를 지나는 발판"의 집합을 std::vector 등으로 관리하면, 이 시각들을 전부 전처리할 수 있다.

이 과정에서 중국인의 나머지 정리가 사용된다. 이제 다익스트라를 사용하는데, "특정 발판에 올라올 수 있는 최소 시각"을 보면 된다.

다른 풀이가 있는 것으로 아는데, 중국인의 나머지 정리 템플릿이 있으면 이 풀이가 더 쉬운 것 같다.

BOJ 19302 XOR Transformation

$F_K^1$, $F_K^2$, $F_K^4$ 등을 손으로 계산해보면 핵심적인 패턴을 찾을 수 있다. 

결국 이진 거듭제곱과 같은 계산과 함께, 부분합을 계산하여 풀 수 있는 문제가 된다. 

구현이 조금 귀찮은 문제다. $2^t$를 간격으로 하는 부분합을 구해야 하는데 여기서 사이클이 여러 개 생길 수 있어서다.

BOJ 19390 Coprime Queries

뭔가 오프라인 + 자료구조 같은 덜 수학적인 풀이가 있을 것 같지만, 나는 걍 수학으로 밀었다.

문제의 해결을 온라인으로 한다. 우선 답에 대해서 이분탐색을 할 수 있음을 알 수 있다.

이제 $a_m, a_{m+1}, \cdots , a_r$ 중에서 $x$와 서로소인 것이 존재하는지 판별하면 된다. 이를 위해서는

$$\sum_{i=m}^r [\text{gcd}(a_i, x)= 1] = \sum_{i=m}^r \sum_{d|\text{gcd}(a_i, x)} \mu(d)$$

$$= \sum_{d|x} \mu(d) \cdot \left( \sum_{i=m}^r [d|a_i] \right) = \sum_{d|x} \mu(d) \cdot (cnt_d(r) - cnt_d(m-1))$$

를 계산하면 된다. 여기서 $cnt_d(m)$은 $a_1, a_2, \cdots, a_m$ 중 $d$의 배수의 개수를 의미한다.

이 값은 약수를 전처리하고 특정 값의 배수의 위치를 std::vector에 저장하고 lower_bound를 쓰는 것으로 빠르게 계산할 수 있다.

이걸 그대로 짜면 애석하게도 TLE가 발생하고, 약수를 관리하는 과정에서 $\mu(d) \neq 0$인 것만 사용하면 AC.

BOJ 19138 GCD vs LCM

식을 정리해보자. 우리가 계산하고자 하는 값은 결국에

$$\sum_{1 \le i \le n, 1 \le j \le m, \text{gcd}(i, j) \le a} \text{lcm}(i, j) = \sum_{g=1}^a \sum_{i=1}^{n/g} \sum_{j=1}^{m/g}  gij \cdot [\text{gcd}(i, j) = 1]$$

$$= \sum_{g=1}^a \sum_{i=1}^{n/g} \sum_{j=1}^{m/g} gij \cdot \sum_{d|\text{gcd}(i, j)} \mu(d)  = \sum_{g=1}^a \sum_{d=1}^{\text{min}(n, m)/g} \sum_{i=1}^{n/gd} \sum_{j=1}^{n/gd} gd^2ij \cdot \mu (d)$$

$$= \sum_{g=1}^a \sum_{d=1}^{\text{min}(n, m)/g} gd^2 \mu(d) \cdot \binom{ \lfloor n/gd \rfloor +1 }{2} \cdot \binom{ \lfloor m/gd \rfloor + 1}{2}$$

$$= \sum_{T=1}^{\text{min}(n, m)} \sum_{g|T, g \le a} T \cdot (T/g) \cdot \mu(T/g) \cdot \binom{ \lfloor n/T \rfloor + 1}{2} \cdot \binom{\lfloor m/T \rfloor + 1}{2}$$

$$= \sum_{T=1}^{\text{min}(n, m)} T \cdot \binom{ \lfloor n/T \rfloor + 1}{2} \cdot \binom{\lfloor m/T \rfloor + 1}{2} \cdot \left( \sum_{g|T, g \le a} (T/g) \cdot \mu(T/g) \right)$$

이제 문제를 해결할 수 있다. 기본적으로 $a$에 대한 조건이 없다면, 이는 $n/T$, $m/T$로 가능한 값이 적다는 점을 이용해서 구간을 나누고, 각 구간에 대한 $f(T) = \sum_{g|T} (T/g) \cdot \mu(T/g)$의 부분합을 미리 전처리하여 해결할 수 있다. 이러면 쿼리 당 루트 시간에 문제를 풀 수 있다.

문제는 $a$에 대한 조건이다. 이를 위해서, 쿼리를 오프라인으로 해결하자. 쿼리를 $a$ 기준으로 정렬한다.

이제 다시 $f(T) = \sum_{g|T, g \le a } (T/g) \cdot \mu(T/g)$라고 정의하자. 이제 잘 생각해보자.

$a$가 증가하면 $a$의 배수인 $T$에 대하여 $f(T)$의 값이 변한다. 조화수열을 생각하면 변화 횟수는 많지 않다.

맨 처음의 식으로 돌아가서, 우리가 계산해야 하는 것은 결국 특정 구간에 속한 $T$에 대한 $f(T)$의 값들의 합이다. 

그러니 결국 점 업데이트 + 구간 쿼리 문제가 되고, 이는 단순한 세그먼트 트리를 이용하여 해결할 수 있다.

BOJ 19495 Square Function

수학 대회 기출에서 가져온 문제지만 어쨌든 좋은 문제는 맞는 것 같다. 다음 관찰을 순서대로 해야한다. 증명은 생략.

1. $S(x)$는 단사함수다. 이 문제는 Putnam 2013 A2 문제이기도 하다. 여기까지는 쉽다.

2. $S(x)$는 사실 자연수에서 소수가 아닌 자연수로 (즉 1 포함) 가는 전단사함수이다. 이건 조금 까다롭다.

3. 2를 증명하는데 중요한 관찰은 다음 사실이다. $x$가 소수가 아닌 자연수라 하자. $x = t_1 > t_2 > \cdots > t_k$가 있어 $t_1 \cdot t_2 \cdots t_k$가 제곱수가 되도록 하는 $t_k$의 최댓값을 $T(x)$라고 하자. 이 값이 잘 정의됨을 보이는 것은 어렵지 않다. 이때, $S(T(x)) = x$가 성립함을 보일 수 있다. 

결국 문제는 $y$가 소수인지 판별하고, 아니면 $T(y)$를 구하는 문제가 된다. 이제 이 문제와 비슷해진다.

이 문제의 근본적인 해결 방법은 소인수의 지수들의 홀짝성을 $\mathbb{F}_2$의 벡터로 보는 것이다.

답에 대해서 이분탐색을 하자. 그러면 $m, m+1, \cdots , y-1$의 이진 벡터를 선형결합하여 $y$의 벡터를 만들 수 있는지 판별하는 문제가 된다.

이를 위해서는 가우스 소거를 할 필요가 있는데, 여기서 중요한 관찰이 하나 더 필요하다.

어쨌든 $1000$ 이상의 소수를 2개 이상 가질 수는 없다는 것이다. 그러니 모든 벡터를 $1000$ 이하 소수 200개쯤에 대한 벡터와 "내가 특별히 가지고 있는 $1000$ 이상 소수 하나 (없을 수도 있음)"으로 보는 것이 좋다. 이 관찰로 시간복잡도를 획기적으로 줄일 수 있다.

이 점을 고려하면 가우스 소거를 매우 효율적으로 할 수 있으며, std::bitset으로 최적화를 하면 문제가 해결된다.

문제에서 등장하는 수열은 OEIS에도 있는 수열로, 레퍼런스를 보면 관련 문제가 수학 잡지에도 등장한 것으로 보인다.

AGC 047

정말 오랜만에 rated round를 쳤다. 앳코더나 코포나 레이팅이 변하는 라운드는 2018년 초 이후로 처음이다.

문제가 조금 별로였고, 그런 라운드만 잘 치는 나는 덕분에 나쁘지 않게 대회를 쳤다.

C, A를 빠르게 해결한 것에 비해 B, D가 느렸는데, 풀이를 빠르게 찾았지만 구현에서 뇌절을 한 것이 컸다.

15분을 남겼을 때 E small을 읽고 풀려고 했는데, 손을 놓아버린 것도 아깝다. E small까지는 풀었어야 했다고 본다. ㄲㅂ

• A : 어쨌든 중요한 것의 2, 5의 개수이므로 이것만 잘 따지면 된다. $cnt[a][b]$를 2가 $a$개, 5가 $b$개인 수의 개수라고 하면 된다. 중복 카운팅을 조심해서 처리하자. 파싱하는 게 가장 어렵고 귀찮은 개노잼 문제다. 예전에는 무슨 가우스 소거를 A에 내더니 뭔...
• B : $S$가 $T$로 갈 수 있는 필요충분조건은, (단, $S \neq T$ 가정) 우선 당연히 $|S| > |T|$이고, $T$의 길이 $|T|-1$ suffix가 $S$의 길이 $|T|-1$ suffix와 같아야 하며, $T$의 첫 글자가 $S$의 첫 $|S|-|T|+1$개의 글자에서 존재해야 한다. 이를 기반으로, 해시를 해서 문제를 해결할 수 있다. suffix의 hash와 대응되는 prefix에 존재하는 알파벳에 대하여 카운트를 늘려주면, 이를 통해서 답을 구할 수 있다. 이를 단순하게 하면 TLE가 발생하고, 실제로 관심이 있는 해시 값인 각 문자열 $S_i$의 길이 $|S_i|-1$ suffix의 hash에 대해서만 계산하면 통과된다. 모든 문자열을 뒤집고 Trie를 써도 된다.
• C : 곱셈을 덧셈으로 바꾸면 FFT가 가능할 것 같다. 이를 가능하게 하는 도구는 로그다. 근데 정수론 문제니까 그냥 로그말고 이산로그를 쓰면 된다. $P$의 값이 작으므로, 문제 없다. 원시근은 $2$를 쓰면 된다. 걍 개노잼...
• D : 개인적으로는 재밌게 풀었던 문제. 더 좋은 풀이가 많은 것 같으니 한 번 확인할 필요는 있겠다. 일단 $DP[i]$를 $i$에서 위로 올라가서 $1$까지 곱한 값이라고 하고, $IV[i]$를 $DP[i]$의 잉여역수라고 하자. 그러면 우리가 구해야 하는 값은 각 $1 \le i <  j \le L$에 대하여 $\frac{DP[L+i-1] \cdot DP[L+P[i]-1] \cdot DP[L+j-1] \cdot DP[L+P[j]-1]}{DP[LCA(L+i-1, L+j-1)] \cdot DP[LCA(L+i-1, L+j-1)/2] \cdot DP[LCA(L+P[i]-1, L+P[j]-1)] \cdot DP[LCA(L+P[i]-1, L+P[j]-1)/2]}$를 합한 값이다. 식이 어마어마하게 더러운데, 천천히 생각해보자. 우선 $i$를 고정하고, $LCA(L+i-1, L+j-1)$을 고정해보자. 이렇게 되면 가능한 $j$의 영역이 구간을 이루게 된다. 우리가 여기서 걱정해야 하는 것은 $DP[L+j-1]  \cdot DP[L+P[j]-1]$의 값과, $LCA(L+P[i]-1, L+P[j]-1)$의 위치이다. 그런데 $LCA(L+P[i]-1, L+P[j]-1)$의 위치를 고정하면, 원하는 $P[j]$의 위치도 일종의 구간이 된다. 그러니 결국 "$j$의 구간, $P[j]$의 구간이 주어졌을 때 그 안에서 $DP[L+j-1] \cdot DP[L+P[j]-1]$의 합을 구하라"는 문제가 된다. 이는 Persistent Segment Tree로 할 수 있다. 이러면 $2^H H^3$ 풀이가 완성되는데, 이를 최적화할 수 있다. 아까도 말했지만 $P[j]$의 구간에 따라서 LCA의 위치가 달라지는데, 이 구간이 이진트리 특성상 어마어마하게 깔끔하다. 그래서 사실 PST를 위에서부터 내려가는 것으로 $P[j]$의 구간에 따른 각 쿼리를 로그 시간에 전부 해결할 수 있다. 그래서 $H$ 하나가 빠지고 $2^H H^2$ 풀이가 나온다. 끝. 나의 경우 PST의 초기 크기를 단순히 $2^{17}$로 잡지 않고, $2^{H-1}$로 정확하게 잡는 것이 중요했다. 이걸 놓쳐서 디버깅이 힘들었다. 다이아 5 ~ 다이아 4 정도 되는 문제 같은데 그래도 시간 안에 해결했다는 점은 긍정적이다.
• E : 재밌어 보이는 문제인데, 먼 미래에 업솔빙을 하는 것으로...

출처는 잘 모르는 문제. 

입력으로는 $a, N$이 주어지며, 이때 $1 \le x \le y \le N$, $\text{gcd}(x, y)=1$, $x|y^2+a$, $y|x^2+a$를 만족하는 $(x, y)$의 개수를 구해야 한다. 

$1 \le a \le 10^5$, $1 \le N \le 10^{18}$. 테케는 총 $10^6$개가 있으며, 전부 5초 내에 해결해야 한다. 메모리 제한은 256MB.

우선 $x|y^2+a$, $y|x^2+a$란 조건은 $\text{gcd}(x, y)=1$과 함께 생각했을 때, $xy|(x^2+y^2+a)$라는 것으로 바꿀 수 있다.

이제 이는 수학 올림피아드 계에서는 유명한 비에타 점핑 테크닉을 쓸 수 있는 문제가 된다.

$x^2+y^2+a=kxy$가 성립한다고 하고, 이를 만족하는 $x+y$가 가장 작은 순서쌍 $(u, v)$를 생각하자. WLOG, $u \ge v$다.

그런데 생각해보면 $(u, v)$가 조건을 만족하면, $(kv-u, v)$ 역시 조건을 만족하고, 이때 $kv-u = (v^2+a)/u$다.

그런데 최소성의 조건에서 $(v^2+a)/u \ge u$가 성립하고, $v^2+a \ge u^2$을 얻는다. 

즉, $x^2+y^2+a=kxy$를 만족함과 동시에 $y^2 \le x^2 \le y^2+a$를 만족하는 $(x, y)$를 전부 구하면, 이 해들이 "기본해"가 된다.

이는 $a \le 10^5$이므로 약수를 전처리하고 lower bound 등을 잘 활용하는 것으로 후보군을 줄여서 잘 계산할 수 있다.

이제 이 "기본해"를 가지고 각 $a$에 대한 해를 전부 생성하고, std::vector에 저장하자. 

쿼리에 대답하는 것은 간단한 lower bound로 해결할 수 있다. 시간/메모리가 모두 빡빡해서 조심히 구현해야 한다.