import sys
import math
input = sys.stdin.readline
N = int(input())
if int(math.sqrt(N)) - math.sqrt(N) == 0:
print(-1)
else:
cnt1 = 0
#N이 빗변인 경우
for i in range (1,int(math.sqrt(N/2))+1):
j = N - i**2
#j가 어떤 정수의 제곱꼴인지 판단하는 방법#
if math.sqrt(j) - int(math.sqrt(j)) == 0:
cnt1 += 1
else:
continue
#N이 빗변이 아닐 경우
#N = B ** 2 - A ** 2 = (B+A)(B-A)로 계산된다. 두 수의 기우성이 동일해야함.
cnt2 = 0
for i in range (1,int(math.sqrt(N))+1):
if N % i == 0:
if (i + (N // i)) % 2 == 0:
if i == N // i:
continue
else:
cnt2 += 1
else:
continue
print(cnt1 + cnt2)
얼마전 고대 프로그래밍 기출 문제.
먼저, 이러한 순서쌍이 무한히 존재하는 경우는 쉽게 찾을 수 있는데,
주어진 N이 제곱수인 경우에 순서쌍이 무한히 존재하는 것을 용이하게 확인할 수 있다.
(예를 들어서, N = 4인 경우에는 한변의 길이가 2이고, 나머지 두 변중 하나의 길이가 정수이기만 하면되므로, 무한히 만들 수 있다. 왜냐하면 길이 2인 변을 빗변이 아닌 변으로서 생각하면 OK)
한편, N이 제곱수가 아닌 경우에는 케이스를 나눠보아야한다.
Case 1. N이 어떤 두 제곱수의 합으로 이루어져있는지 확인 (즉, 루트 N이 빗변인 경우)
Case 2. 루트 N이 빗변이 아닌 경우. 이때, 우리는 나머지 두 변이 "반드시" 정수가 되어야하는 부분에 주목할 수 있다.
즉, N = B^2 - A^2 = (B + A)(B - A) 로 둘 수 있다.
(여기서 B는 빗변의 길이, A는 남은 변의 길이)
여기서 한가지 수학적인 성질이 더 쓰이게 되는데 바로 '기우성'이다.
B + A, B - A는 같은 기우성을 지니고 있다. 둘 중 한쪽이 홀수라면 나머지 한쪽도 반드시 홀수여야하고, 한쪽이 짝수라면 나머지 한쪽도 짝수이어야한다.
그리고, A는 0이 아니므로 B + A > B - A가 성립하는 것을 알 수 있다.
여기서 뭔가 보이는가? 그렇다. 바로 약수찾기 문제에 귀결하게 된다.
즉, N = 96으로 예를 들어보면 96 = 96 x 1 = 48 x 2 = 32 x 3 = 24 x 4 = 16 x 6 = 12 x 8
이런 식으로 나타낼 수 있다.
이때 B+A = 48, B-A = 2 < OK
B+A = 32, B-A = 3 < FAIL (왜냐하면 두 수의 홀짝성이 다르기때문)
B+A = 24, B-A = 4 < OK
B+A = 16, B-A = 6 < OK
B+A = 12, B-A = 8 < OK
이렇게 되는 것을 확인할 수 있겠다 !
마지막으로 Case1의 카운트 수와 Case2의 카운트 수를 서로서로 더해준다면 끝 ! (갯수가 유한한 경우)
'코딩' 카테고리의 다른 글
[BOJ] 백준 10422 괄호 Python (1) | 2023.10.28 |
---|---|
[BOJ] 백준 28427 Tricknology Python (1) | 2023.10.28 |
[BOJ] 백준 20157 화살을 쏘자! Python (0) | 2023.10.28 |
[BOJ] 백준 29733 3차원 지뢰찾기 Python (0) | 2023.10.28 |
[BOJ] 백준 1011 Fly me to the Alpha Centauri Python (0) | 2023.10.28 |