[BOJ 20704] Find a Square

문제를 접근하는 방법은 각 소수$q$에 대해서 $ax^{2}+bx+c \equiv 0\pmod{q}$를 만족하는 $x$를 찾는 것이다. 그럼 소수 $q$는 어느 범위까지 검사해야할까? 문제에서 구하라고 하는 것은 주어진 곱을 나누는 제곱수이다. 적절한 커팅을 이용해서 확인해 봐야 하는 소수의 개수를 줄이도록 하자. $(an^{2}+bn+c)^{1/3}$보다 작은 소수들을 모두 검사한다고 하자. 어떤 수 $x$가 어떤 자연수 $k$에 대해서 $ax^{2}+bx+c=p\cdot k$를 만족한다고 하자, 그럼 에라토스테네스의 체처럼 $(an^{2}+bn+c)^{1/3}$ 보다 작은 소수들로 각 $p(x)$들을 나누자. 남은 $p(x)$들은 $(an^{2}+bn+c)^{1/3}$보다 큰 소수 2개의 곱으로 이루어져 있거나 그 자체로 소수이다. 만약 앞서 말한 소수 2개가 같은 수라면 $ax^{2}+bx+c=q^{2}$을 만족해야한다. 이런 케이스는 직접 $x$들을 대입하여 소수의 제곱이 되는지 확인하자. (이 케이스를 빠르게 해결하는 팁은 제곱수들은 반드시 $10$으로 나눈 나머지가 $1,5,9$중 하나라는 것이다.) 위 케이스를 제외하면 남은 경우는 $p(x)$가 소수거나 서로 다른 두 소수의 곱인 것이다. 그렇다면 $(an^{2}+bn+c)^{1/3}$보다 큰 소수들은 반드시 서로 다른 $x,y$에 대하여 $p(x),p(y)$를 나누어야 한다. 이를 만족하는 소수를 $q$라고 하면 $ax^{2}+bx+c\equiv ay^{2}+by+c \pmod{q}$에서 $(x-y)(a(x+y)+b)\equiv 0\pmod{q}$를 얻는다. 만약 $q|(x-y)$이면 $q\le n$임을 알 수 있다. 만약 $q|a(x+y)+b$라면, $q$는 $x\le 2n$을 만족하는 $ax+b$들의 소인수들을 구함으로써 얻을 수 있다. $\sqrt{2an+b}$보다 작은 소수들을 우리가 구했고 이 소수들로 각 $ax+b$를 나누어 소인수들을 구했다고 하자. 그럼 위의 소수들로 나누어지지 않은 $ax+b$는 $\sqrt{2an+b}$보다 큰 소수 $q$와 어떤 수 $k$에 대하여 $ax+b=qk$가 되며 $k$는 반드시 $\sqrt{2an+b}$보다 작아야 한다. 즉, $k=1$이 되며, 검사되지 않은 수들은 모두 소수가 된다. 따라서 이들을 검사하면 모든 가능한 소인수들을 검사할 수 있다. 즉, 우리가 검사해야 하는 소수들은 최대 $\pi(\max\{(an^{2}+bn+c)^{1/3}, n, \sqrt{2an+b}\})+2n$개 임을 알 수 있다. 

 

$ax^{2}+bx+c \equiv 0\pmod{q}$를 해결하는 방법은 Tonelli-Shanks 알고리즘을 사용하면 된다. 각 소수에 대해서 주어진 방정식의 솔루션을 찾고 그에 해당하는 인덱스들에 대해 trial division을 해서 주어진 곱을 나눌 수 있는 최대의 지수를 찾아내자!

 

P.S. 문제를 처음 해결하고 나서 최대로 확인할 소수의 값을 $13*10^{5}$이 아닌 $17*10^{5}$으로 두었더니 해결되었다. 지금은 구현의 오류를 수정하였으나 $17*10^{5}$이라고 제출한 코드도 여전히 맞았습니다를 받는 것이 맘에 들지 않는다. $17*10^{5}$ 코드를 틀리게 하는 방법은 간단하다!! $a,b,c,x$를 잘 찾아서 $ax^{2}+bx+c$가 $17*10^{5}$보다 큰 소수의 제곱으로 나누어지게 하면 된다. 귀찮은데... 누군가 해주지 않을까?