Codeforces Round 844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round) - D. Many Perfect Squares (1800)
어떤 두 쌍을 보려는 생각은 했는데 식을 전개를 못시켰다. 에디토리얼을 보자.
어떤 두 쌍에 대해 $i<j$, $a_i+x$와 $a_j+x$ 가 완전제곱수가 될 수 있는지 보자.
$a_i+x=p^2,\ a_j+x=q^2$ 가 된다고 하자.
$a_j-a_i=q^2-p^2=(q-p)(q+p)$ 이다.
이는 $q-p$가 $a_j-a_i$의 양의 약수임을 보인다.
$a_j-a_i$의 모든 약수들을 $O(\sqrt{ a_j-a_i })$ 에 순회할 수 있다.
어떤 약수 $d$에 대해 단순한 $p,q$에 대한 이차연립방정식을 풀어보자.
$$
\begin{cases}
q-p=d \\
q+p=\dfrac{a_j-a_i}{d}
\end{cases}
$$
이걸 풀면
아니 진짜 연립방정식을 푸는 문젠지 몰랐다;
$$
\begin{cases}
p=\dfrac{1}{2}\left( \dfrac{a_j-a_i}{d}-d \right) \\
q=\dfrac{1}{2}\left( \dfrac{a_j-a_i}{d}+d \right)
\end{cases}
$$
이다.
만약 $p,q$ 모두 정수라면 우린 $x$의 후보로 $p^2-a_i$와 $q^2-a_j$ 를 포함할 수 있다.
이걸 모두 브루트포스로 돌려버리면 된다.
시간복잡도를 좀 보자.
$O(n^2 \cdot \sqrt{ 10^9 } \cdot n \cdot \log 10^{18})$ 정도이다. 제곱수인지는 이분탐색으로 찾아주면 된다.
Comments