[BOJ 18578] Jimp Numbers

주어진 식을 다음과 같이 변형하자. 이때 $x>y$ 임에 주의하자.

\[(x-y)^{2}+x^{2}+n=(x+y)^{2}\]

\[n=x(4y-x)\]

여기서 $x|n$을 얻는다. 또

\[4|(\frac{n}{x}+x)=4y\]

$x>y$조건에서 다음을 얻는다. 

\[y=\frac{\frac{n}{x}+x}{4}<x \implies \sqrt{\frac{n}{3}}<x\le n\]

위 세 조건을 만족시키는 $x$가 유일하게 존재할 때 $n$이 Jimp Number가 됨을 이용하자.

 

1. $n\equiv 1\pmod{4}$인 경우

$x$를 4로 나눈 나머지가 1인 경우와 3인 경우가 존재하는데 각 경우 모두 $\frac{n}{x}+x$를 4로 나눈 나머지가 2가 되어 Jimp Number가 될 수 없다.

 

2. $n\equiv 3\pmod{4}$인 경우

마찬가지 방법으로 하면 어느 경우에서든 1번째 조건을 만족함을 확인할 수 있다. 이미 $x=n$일 때 해가 존재하므로 다른 $x$가 $(\sqrt{\frac{n}{3}},n)$에 존재하면 안된다. 이 말은 $n$이 소수라는 것을 쉽게 알 수 있다.

 

3. $n\equiv 2\pmod{4}$인 경우

$x$가 홀수거나 짝수일 때로 나누자. 그럼 두 경우 모두 첫 번째 조건에서 틀리게 된다.

 

4. $n=4v$($v$는 홀수)인 경우

- $v=1$인 경우

이때 $n=4$이고 Jimp가 됨을 쉽게 볼 수 있다.

- $v>1$인 경우

$q$를 $v$의 최소 소인수라고 하고 $n$을 Jimp라고 가정하자. 이때 $x=\frac{n}{2}$로 잡으면 1번 조건을 만족하게 되고

\[\sqrt{\frac{n}{3}}<\frac{n}{2} \Leftrightarrow 4\le 3n\]

이기 때문에, 2번 조건도 만족하게 된다. $v=qz$라고 하자. $x$가 유일하게 존재한다는 조건을 이용하면 $\frac{n}{2q}<\sqrt{\frac{n}{3}}$에서 $z\le \frac{q}{3}$을 얻는다. $q$가 $v$의 최소 소인수였으므로 $z=1$을 얻는다. 따라서 $n=4q$가 되며 $\frac{n}{4}$가 홀수인 소수가 될때 Jimp가 된다.

 

5. $n=8v$($v$는 홀수)인 경우

이게 Jimp가 되려면 $(x,\frac{n}{x})$쌍이 각각 $(2\cdot (odd),2\cdot(odd)),(4k,4m)$이어야 하는데 두 경우 모두 불가능하다.

 

6. $n=16v$($v$는 홀수)인 경우

- $v=1$인 경우

$n=16$이고 Jimp가 됨을 쉽게 알 수 있다.

- $v>1$인 경우

$q$가 $v$의 최소인수가 되도록 하자. $x=n/4$일 때 $\sqrt{\frac{n}{3}}\le \frac{n}{4} \implies \frac{16}{3}\le n$으로 해가 존재한다. $v=qz$라고 두자. 그럼 $x=4z$거나 $x=4q$인 상황을 고려할 수 있다. 이때 $4z,4q$는 동시에 $\sqrt{\frac{n}{3}}$보다 작을수 없음이 자명하다. 하지만 이미 해가 존재하므로 $z\ne 1$이면 모순이 될 것이다. 따라서 $z=1$이며 $n=16q$이다. 즉, $\frac{n}{16}$이 홀수인 소수인 경우 Jimp가 된다.

 

7. $32|n$인 경우

$n=32v$라고 하자. 다음 두 쌍을 $(4,8v),(8,4v)$라고 하자. 그럼 두 경우 모두 1,2 번째 조건을 만족시킨다. 즉, 해가 적어도 2개있다. 따라서 Jimp가 아니다. 

 

즉, 구해야하는 것은 임의의 $N$이하의 $4n+3$꼴 소수의 개수와 그냥 소수의 개수이다. 이는 Lucy-HedgeHog알고리즘을 이용하면 쉽게 풀 수 있다.