Loading [MathJax]/jax/output/CommonHTML/jax.js

[BOJ 18578] Jimp Numbers

2023. 3. 4. 23:59PS/백준

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

(xy)2+x2+n=(x+y)2

n=x(4yx)

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

4|(nx+x)=4y

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

y=nx+x4<xn3<xn

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

 

1. n1(mod4)인 경우

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

 

2. n3(mod4)인 경우

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

 

3. n2(mod4)인 경우

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

 

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

- v=1인 경우

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

- v>1인 경우

qv의 최소 소인수라고 하고 n을 Jimp라고 가정하자. 이때 x=n2로 잡으면 1번 조건을 만족하게 되고

n3<n243n

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

 

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

이게 Jimp가 되려면 (x,nx)쌍이 각각 (2(odd),2(odd)),(4k,4m)이어야 하는데 두 경우 모두 불가능하다.

 

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

- v=1인 경우

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

- v>1인 경우

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

 

7. 32|n인 경우

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

 

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

'PS > 백준' 카테고리의 다른 글