rkm0959

중요한 사실은 어쨌든 $T = xor(A) \oplus xor(B)$가 고정값이라는 것이다. 

만약 특정 비트가 $T$에서 꺼져있다면, 뭘 하더라도 $xor(A), xor(B)$는 그 비트에서 같은 값을 갖는다.

다른 말로 하면, 그 비트는 우리가 굳이 신경쓰지 않아도 된다는 것이다. 알아서 강제되기 때문이다.

이제 $T$의 가장 큰 비트를 $xor(A)$에게 준다고 하자. 이 시점에서 $xor(A) > xor(B)$는 강제된다.

이제부터 우리의 목표는 $T$에서 켜진 비트를 최대한 $B$에게 주는 것이다. 이를 확인하려면 뭐가 필요할까?

"특정 상위 비트에 대해서 이 비트마스크를 가질 수 있는가"를 판별하는 방법이 필요하다.

주어진 수들을 체 $\mathbb{F}_2$ 위의 벡터로 보고 기저를 만들자. 이제 가우스 소거로 이걸 할 수 있다. 

결국 XOR prefix를 두 개로 쪼개서, 그 합을 최대화하는 것을 목표로 한다. 문제를 다르게 표현해보자.

어쨌든 쪼갠 두 값의 XOR 값을 고정이다. 또한, 첫 부분은 결국 이전에 등장한 XOR prefix가 된다.

즉, 값 $A$와 집합 $S$가 주어졌을 때, $x \in S$에 대하여 $x + (A \oplus x)$의 값을 최대화한다고 생각하자.

그런데 $x + y = x \oplus y + 2 (x \land y)$가 성립한다. 그러니 $x \land (A \oplus x)$를 최대화한다.

이건 결국, "$A$가 가지지 않는 비트 중 $x$가 갖는 비트"의 값을 최대화하는 문제가 된다.

마찬가지로 큰 비트부터 보면서, "이 mask를 포함하는 원소가 $S$에 존재하는가"를 물어보면 된다.

그런데 $S$는 쿼리를 대답하면서 커지는 집합이므로, 원소를 추가하면서 BFS를 조지면 이 쿼리를 쉽게 답할 수 있다. 

모든 간선을 $0$으로 만드는 것은, 모든 정점의 "인접한 간선들의 가중치의 XOR"을 $0$으로 만드는 것과 동치다.

증명을 하려면, 단순히 리프부터 시작해서 올라가면 된다. 애초에 사이클이 없으니 자명하다.

이제 이 값을 정점의 값으로 부르도록 하자. 이제부터 간선에 대한 생각을 버린다.

또한, 특정 경로에 속한 간선들에 $x$를 XOR하는 것은, 경로의 양쪽 끝점의 값에 $x$를 XOR하는 것과 같다.

이제 훨씬 문제가 편해졌다. 이때 큰 가정을 하나 하자. 정점의 값이 같은 것이 2개가 있는 경우, 한 번의 시행으로 두 값을 $0$으로 만들 수 있다. 

이 시행을 무조건 하는 것이 이득이라고 가정해보자. 이제 문제를 풀 수 있다.

이 가정의 장점은, 현재 상태를 비트마스크로 쓸 수 있다는 것이다. "현재 홀수 개 존재하는 값의 집합"으로 보면 된다.

시작하자마자 같은 값을 갖는 정점 2개를 쌍으로 묶어 전부 0으로 만들고, 각 값이 최대 한 번 존재하도록 한다.

이제 "두 정점을 잡아 $x$를 XOR한 후, 두 개 이상 존재하는 값을 묶어 처리"하는 것을 상태 이전으로 볼 수 있다.

이러한 상태 이전은 그래프의 정점 (비트마스크) 사이의 간선으로 볼 수 있고, 이제 최단 거리 문제가 된다. 끝.

$$E(f(s_1, s_2, \cdots, s_n)) = E( \sum_{k=1}^\infty [\exists_{1 \le i < j \le n} LCP(s_i, s_j) \ge k ])$$

$$ = \sum_{k=1}^\infty P(\exists_{1 \le i < j \le n} LCP(s_i, s_j) \ge k) = \sum_{k=1}^\infty \left( 1 - P(\forall_{1 \le i < j \le n} s_i[0,k) \neq s_j[0, k)) \right) $$

$$ = \sum_{k=1}^\infty \left( 1 - \frac{2^k(2^k-1) \cdots (2^k-n+1)}{(2^k)^n} \right) $$

가 되며 이는 전개 후 등비수열의 합으로 풀 수 있다. FFT를 쓰면 subquadratic 풀이도 가능. (분할정복/스털링 등)

근본적으로 EGF를 생각하기 편한 구조가 되겠다. 우리가 원하는 EGF는 결국 $$ \prod_{i=1}^{k-1} \left( \sum_{j=0}^n \frac{g_{i, j}}{j!} x^j \right) $$가 된다. 여기서 $g$ 값들이 하나씩 바뀌는 것이 문제다. 모듈로가 NTT 모듈로고, 작으므로, 이 문제의 요령을 생각하자.

이제부터 적용할 모든 NTT는 다항식의 차수와 관계 없이 무조건 $2^{17}$으로 생각한다. 

그러면 NTT는 다항식 $f$가 주어지면 $f(w^0)$부터 $f(w^{2^{17}-1})$을 제공한다. 단, $w=t^6$이며 $t$는 원시근.

그러니 보통 우리의 요령은 각 $k-1$개의 다항식을 NTT하고, 그 결과를 pointwise 곱한 다음 역 NTT를 얹는 것이다.

그런데 이제 다항식이 바뀐다. 다행인 점은, 쿼리마다 다항식이 $k-1$개 중 하나만 바뀌고, 조금만 바뀐다는 것이다.

애초에 바뀌는 양이 단항식 하나라서, $f$ 값을 $\mathcal{O}(2^{17})$ 시간에 바꿔줄 수 있다.

또한, 바뀐 후의 pointwise 곱 역시 해당 위치 $k-1$개의 값 중 $0$의 개수 등을 관리하면 효율적으로 계산할 수 있다.

이렇게 하면 $g$ 값이 뒤집힌 이후에도 pointwise 곱 결과가 얼마인지를 빠르게 관리할 수 있다.

이제 이 결과를 전부 합친다음, 역 NTT를 하자. 여기서 NTT가 선형사상임을 이용하였다. 이러면 끝. 나쁘지 않다.  

카탈란 문제니까 카탈란처럼 접근하자. $n$각형에서 빨간색 영역의 개수의 총합을 $f(n)$, 파란색 영역의 개수의 총합을 $g(n)$이라 하자.

$P_1P_2$가 속한 삼각형이 $P_1P_2P_k$라고 하자. 이 영역은 빨간색이 될 것이며, 양쪽은 $k-1$각형, $n-k+2$각형이 된다.

그러니 이때 추가되는 빨간색 영역의 개수는 $C_{k-3}C_{n-k} + C_{k-3} g(n-k+2) + C_{n-k} g(k-1)$이 된다.

이를 정리하면 $f(n) = \sum_{k=3}^n \left( C_{k-3}C_{n-k} + C_{k-3}g(n-k+2) + C_{n-k}g(k-1) \right) = C_{n-2} + 2 \sum_{k=0}^{n-1} C_k g(n-1-k)$가 된다. 

비슷하게 $g(n) = 2 \sum_{k=0}^{n-1} C_k f(n-1-k)$가 성립한다. 매우 생성함수가 필요해보이는 식이다.

그런데 그 전에 주의가 필요하다. 이 식만 보면 $f(2)=1$인데, 실제로는 $f(2)=0$이다. (index 문제) 나머지는 문제가 없다.

카탈란 수에 대한 생성함수를 $T(x)$, $f$에 대한 생성함수를 $F(x)$, $g$에 대한 생성함수를 $G(x)$라 하자.

여기서 우리는 $F(x) + x^2 = x^2 T(x) + 2 x T(x) G(x)$, $G(x) = 2xT(x)F(x)$가 성립한다. 

정리하면 $F(x) + x^2 = x^2T(x) + 4x^2T(x)^2 F(x)$가 성립하고, 결론적으로 $F$를 얻는다.

이를 실제로 계산하려면 $T(x)$를 어느 정도 계산하고, 다항식의 inverse를 계산하는 방법을 적용해야 한다.

이는 다항식 나눗셈 및 multipoint evaluation 등에 활용되는 부분이므로, 알아두는 것도 좋다.

다른 풀이로는 식의 형태를 보고 online FFT 각을 재서 푸는 방법이 있으며, 이 풀이가 정해였다고 한다. 18743번 참조. 

생성함수로 이렇게 풀리는 이상 polynomial coefficient의 recurrence가 존재할 것 같다. 실제로 존재한다. 얘 참고.

그래서 루트, 로그제곱 (online FFT), 로그 (생성함수 계산), 선형 (recurrence 유도) 풀이가 모두 있는 문제가 된다.

이제부터 급수 $f(x)$의 $x^n$의 계수를 $f(x)[x^n]$이라고 표기하도록 하겠다.

이 문제도 생성함수로 접근한다. 그 근거는 convolution에 있는데, 이걸 진짜 convolution으로 생각하면 너무 힘들다.

그냥 생성함수를 생각한 후, 그 함수를 $k$승한 뒤 계수의 부분합을 구하라는 문제로 받아들이는 것이 편하다.

이제 $b_m(n)$의 생성함수를 생각하자. 이는 결국 $(1+x+x^2+ \cdots )(1+x^m+x^{2m}+\cdots) \cdots $와 같다.

그러니 이를 정리하면 $\displaystyle \prod_{t=0}^\infty \frac{1}{1-x^{m^t}}$를 얻는다. 이제 본격적인 풀이를 준비하자. 어쨌든 목표는 $\displaystyle \sum_{i=0}^n \left( \prod_{t=0}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^i]$가 된다.

문제를 오히려 더 어렵게 만들어보자. 다항식 $P$가 있을 때, 이런 계산을 할 수 있다. $$ \sum_{i=0}^n P(i) \cdot \left( \prod_{t=0}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^i] = \sum_{i=0}^n P(i) \cdot \sum_{j=0}^i \left( \frac{1}{(1-x)^{k-1}} \cdot \prod_{t=1}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^j] $$

$$ = \sum_{j=0}^n \left( \sum_{i=j}^n P(i) \right) \cdot \left( \frac{1}{(1-x)^{k-1}} \cdot \prod_{t=1}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^j] $$

$$ = \sum_{i=0}^n P^{*}(i) \cdot \left( \frac{1}{(1-x)^{k-1}} \cdot \prod_{t=1}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^i] $$ 

여기서 $P^{*}$는 $P^{*}(i) = P(i) + P(i+1) + \cdots + P(n)$이 각 $0 \le i \le n$에 대해 성립하는 다항식이다. 

우리는 $P$를 $P^{*}$로 바꾸는 과정에서 $\displaystyle \frac{1}{1-x}$ 항을 하나 털었다. 이걸 $k$번 반복하면,

$$ \sum_{i=0}^n P^{*k}(i) \cdot \left( \prod_{t=1}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^i] = \sum_{i=0}^{\lfloor n/m \rfloor} P^{*k}(m \cdot i) \cdot  \left( \prod_{t=0}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^i] $$

이제 우리는 $P$를 $P^{*k}$로 바꾸면서 ($k$번 적용했다는 뜻이다) $n$을 $\lfloor n/m \rfloor$으로 털었다.

결국 이 과정을 $n=0$이 될 때까지 진행하면 된다. $P$를 $P^{*}$으로 바꾸는 과정을 효율적으로 하기만 하면 된다.

이는 Faulhaber's Formula 등을 통해서 할 수 있다. 적당히 뇌를 써서 효율적으로 하면 여유롭게 통과된다.

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

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

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

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

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

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

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

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

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

이제 $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.

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

$$ \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)$의 값들의 합이다. 

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

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

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에도 있는 수열로, 레퍼런스를 보면 관련 문제가 수학 잡지에도 등장한 것으로 보인다.

정말 오랜만에 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 : 재밌어 보이는 문제인데, 먼 미래에 업솔빙을 하는 것으로...

우선 $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로 해결할 수 있다. 시간/메모리가 모두 빡빡해서 조심히 구현해야 한다.

식부터 세우자. $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 알고리즘으로 답을 전처리할 수 있다. 아예 하드코딩해도 된다. 이제 이를 합쳐서 답을 구하는 것은 쉽다. 벌레캠프 각을 너무 늦게 봐서 해결이 오래 걸렸다.

식을 또 열심히 정리해보자. 우리가 원하는 답은 결국 

$$ \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 같다.
• 소인수를 두 그룹으로 나누고, 양쪽을 "잘 합치는" 방법을 생각해야 한다.
• 이게 생각보다 어려운데, 커팅도 많이 하고 알고리즘 자체도 생각해야 하고 수학도 많이해야 한다.