숫자 n이 주어졌을 때, n의 진약수(proper divisor) 중 하나를 골랐을 때 그 수가 짝수이면서 동시에 완전제곱수일 확률을 구하는 문제입니다.
예를 들어 n = 36이라면 답은 1/8입니다. 36의 진약수는 {1, 2, 3, 4, 6, 9, 12, 18}로 총 8개이고, 이 가운데 짝수이면서 완전제곱수인 수는 4 하나뿐이기 때문입니다.
접근 방법
이 문제의 핵심 아이디어는 다음과 같습니다.
- 모든 짝수 완전제곱수는 반드시 4의 배수입니다. 따라서 n이 4로 나누어떨어지지 않으면 n의 어떤 약수도 조건을 만족할 수 없으므로 바로 0을 반환하면 됩니다.
- n을 소인수분해하여 각 소수의 지수를 구합니다.
- 어떤 약수가 완전제곱수가 되려면 모든 소수의 지수가 짝수여야 하고, 짝수이려면 2의 지수가 2 이상의 짝수여야 합니다.
- 전체 약수 개수에서 1(n 자기 자신)을 빼면 진약수의 개수가 됩니다. 조건을 만족하는 경우의 수도 마찬가지로, n 자신이 완전제곱수라면 하나를 빼주어야 합니다.
- 마지막으로 두 수의 최대공약수(gcd)로 나누어 기약분수 형태로 출력합니다.
알고리즘 단계
- n mod 4 ≠ 0이면 0을 반환합니다.
- nc ← n, ptr ← 2로 초기화하고 빈 리스트 l을 생성합니다.
- ptr ≤ √nc인 동안 다음을 반복합니다.
- a ← 0으로 초기화합니다.
- nc가 ptr로 나누어떨어지는 동안 a를 1씩 증가시키고, nc ← ⌊nc / ptr⌋로 갱신합니다.
- a > 0이면 a를 리스트 l에 추가합니다.
- ptr을 1 증가시킵니다.
- 반복이 끝난 뒤 nc > 1이면 1을 l에 추가합니다(마지막으로 남은 소인수 처리).
- k ← l[0](소수 2의 지수), d ← k + 1, no ← ⌊k / 2⌋로 설정합니다.
- l의 두 번째 원소부터 끝까지 각 i에 대해 d ← d × (i + 1), no ← no × (⌊i / 2⌋ + 1)로 갱신합니다.
- d ← d − 1로 만들어 전체 진약수의 개수를 구합니다.
- n이 완전제곱수라면 no ← no − 1로 n 자기 자신을 제외합니다.
- g ← gcd(d, no)를 구한 뒤 d와 no를 g로 나누어 기약분수로 만듭니다.
- no = 0이면 0을 반환하고, 그렇지 않으면 "no/d" 형태의 문자열을 반환합니다.
파이썬 구현 예시
아래 코드를 통해 실제 구현 방법을 확인해 보겠습니다.
from math import gcd
def solve(n):
# 짝수 완전제곱수는 반드시 4의 배수이므로,
# n이 4의 배수가 아니면 조건을 만족하는 약수가 없음
if n % 4 != 0:
return 0
nc = n
ptr = 2
l = [] # 소인수들의 지수를 저장할 리스트
while ptr <= nc ** 0.5: # 소인수분해 수행
a = 0
while nc % ptr == 0:
a += 1
nc //= ptr
if a > 0:
l.append(a)
ptr += 1
if nc > 1: # 남은 소인수 처리
l.append(1)
k = l[0] # 소수 2의 지수
d = k + 1 # 약수 개수 계산용
no = int(k / 2) # 2의 지수가 2 이상의 짝수인 경우의 수
for i in l[1:]:
d = d * (i + 1)
no *= int(i / 2) + 1 # 지수가 짝수인 경우의 수 누적
d = d - 1 # n 자기 자신 제외 → 진약수 개수
if int(n ** 0.5) ** 2 == n: # n이 완전제곱수면 자기 자신 제외
no -= 1
g = gcd(d, no) # 최대공약수로 약분
d = d // g
no = no // g
if no == 0:
return 0
else:
return str(no) + '/' + str(d)
n = 36
print(solve(n))n = 36일 때 동작 과정 살펴보기
- 36 = 2² × 3²이므로 소인수 지수 리스트는 l = [2, 2]가 됩니다.
- 초기값: k = 2, d = 3, no = ⌊2/2⌋ = 1
- 두 번째 지수 2에 대해: d = 3 × 3 = 9, no = 1 × (⌊2/2⌋ + 1) = 2
- d = 9 − 1 = 8 → 진약수는 총 8개
- 36은 완전제곱수이므로 no = 2 − 1 = 1 → 36 자기 자신은 제외됩니다.
- gcd(8, 1) = 1이므로 약분 없이 그대로 1/8을 반환합니다.
실행 결과
입력:
n = 36
출력:
1/8
이처럼 소인수분해와 약수 개수 공식을 활용하면, 일일이 모든 약수를 나열하지 않고도 O(√n) 시간 안에 확률을 효율적으로 계산할 수 있습니다.