D. Many Perfect Squares

어떤 두 쌍을 보려는 생각은 했는데 식을 전개를 못시켰다. 에디토리얼을 보자.

어떤 두 쌍에 대해 $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

You may also enjoy