2023. 3. 4. 23:59ㆍPS/백준
주어진 식을 다음과 같이 변형하자. 이때 x>y 임에 주의하자.
(x−y)2+x2+n=(x+y)2
n=x(4y−x)
여기서 x|n을 얻는다. 또
4|(nx+x)=4y
x>y조건에서 다음을 얻는다.
y=nx+x4<x⟹√n3<x≤n
위 세 조건을 만족시키는 x가 유일하게 존재할 때 n이 Jimp Number가 됨을 이용하자.
1. n≡1(mod4)인 경우
x를 4로 나눈 나머지가 1인 경우와 3인 경우가 존재하는데 각 경우 모두 nx+x를 4로 나눈 나머지가 2가 되어 Jimp Number가 될 수 없다.
2. n≡3(mod4)인 경우
마찬가지 방법으로 하면 어느 경우에서든 1번째 조건을 만족함을 확인할 수 있다. 이미 x=n일 때 해가 존재하므로 다른 x가 (√n3,n)에 존재하면 안된다. 이 말은 n이 소수라는 것을 쉽게 알 수 있다.
3. n≡2(mod4)인 경우
x가 홀수거나 짝수일 때로 나누자. 그럼 두 경우 모두 첫 번째 조건에서 틀리게 된다.
4. n=4v(v는 홀수)인 경우
- v=1인 경우
이때 n=4이고 Jimp가 됨을 쉽게 볼 수 있다.
- v>1인 경우
q를 v의 최소 소인수라고 하고 n을 Jimp라고 가정하자. 이때 x=n2로 잡으면 1번 조건을 만족하게 되고
√n3<n2⇔4≤3n
이기 때문에, 2번 조건도 만족하게 된다. v=qz라고 하자. x가 유일하게 존재한다는 조건을 이용하면 n2q<√n3에서 z≤q3을 얻는다. q가 v의 최소 소인수였으므로 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인 경우
q가 v의 최소인수가 되도록 하자. x=n/4일 때 √n3≤n4⟹163≤n으로 해가 존재한다. v=qz라고 두자. 그럼 x=4z거나 x=4q인 상황을 고려할 수 있다. 이때 4z,4q는 동시에 √n3보다 작을수 없음이 자명하다. 하지만 이미 해가 존재하므로 z≠1이면 모순이 될 것이다. 따라서 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 > 백준' 카테고리의 다른 글
[BOJ 15174] Hilbert’s Hash Browns (0) | 2023.04.02 |
---|---|
[BOJ 18718] Bags of Candies (0) | 2023.03.11 |
[BOJ 3904] The Teacher's Side of Math (0) | 2022.09.02 |
[BOJ 19549] 레이저 연구소 (6) | 2022.08.21 |
[BOJ 12797] 연금술 (0) | 2022.08.20 |