시험기간에 들어서는 바람에 더욱 격렬히 딴짓을 하고 싶어졌다. 그래서 지금까지 푼 문제보다 어려운 문제를 하나 붙잡고 시험기간에 지칠 때마다 조금씩 풀기로 마음먹었다.
하지만 내 생각대로 되지 않고 도저히 포기를 못하겠어서 그냥 그 자리에 앉아 6시간동안 궁시렁 거린 끝에 겨우 풀어냈다.
일단 이 문제는 실버~골드에 있는 어떤 문제와 매우 비슷했다. 다만, 그 문제는 N의 범위가 10**9정도라 dp와 브루트포스로 어느정도 풀렸지만 해당 문제는 무슨 10**18의 범위를 가지고 있었다. 미친 범위다.
그래서 해당 문제를 dp나 브루트포스로 푼다면 100만년정도 걸릴거같아 다른 알고리즘을 찾게 되었다.
하지만 생각한것처럼 아이디어가 떠오르지 않았다. 그래서 아래 알고리즘 분류를 봤더니 무슨? 매우 익숙한 알고리즘이 있었다. 그리고 보자마자 PTSD가 올라왔다.
분명히 BOJ 13926 gcd(n,k) = 1 에서 봤던 알고리즘이다. 그때 저 미친 폴라드 로하고 밀러라빈 구현하느라 머리카락이 30만개정도 빠졌던 기억이 있어서 좀 많이 당황스러웠다. 게다가 소인수분해와 전혀 관련이 없어보이는 이 문제에 어떻게 적용해야할지를 생각하다보니 매우 막막해졌다.
도저히 답이 안나왔다. 그래서 결국 대 GPT 형님의 힘을 빌리기로했다.
역시 GPT 형님이다. 바로 답이 나온다.
GPT형님 피셜, 라그랑주의 네 제곱수 정리에는 각 제곱수의 개수마다 특징이 있다.
1개로 분리되는 경우, N은 특정 수의 제곱수이다.
2개로 분리되는 경우, N의 소인수를 p라 할 떄 p mod 4의 값이 3인 p의 개수가 만약 짝수개이면, 2개로 분리되지 않는다. 만약 홀수개라면 분리가 가능하다.
4개로 분리되는 경우, N이 다음과 같은 식을 만족하는 경우, 4개로 분리된다. (8k+7)*4^n = N, 즉 인수 4를 모두 없앤 수의 mod 8을 한 결과값이 7이라면 4개로 분리된다.
3개는 1,2,4개로 분리되지 않는 경우이다.
이를 통해 대충 토대가 세워졌다. 1,2,4만 어떻게 판별하면 풀 수 있는것이다. 하지만 1,4는 매우 구현이 간단한 반면, 2개는 구현이 쉽지 않았다.
N의 값이 일단 10**18이하라서 일반적인 소인수분해는 허락되지 않는다. 그래서 시간복잡도가 O(N**1/4)인 폴라드 로가 쓰이는 것이었다. 하지만 폴라드 로는 확정적인 소인수를 반환하지 않는다. 그래서 밀러-라빈 소수 판별법으로 폴라드 로가 뱉은 인수가 소인수인지 판별해 이를 인수분해 해야한다.
그래서 일단 코드의 토대를 짜서 1개, 4개, 3개인 경우는 대충 나눠놓았다.
1개인 경우는 N의 제곱근을 int형으로 변환한 뒤 이를 제곱시켜 N과 비교하는 방식으로 판별했다.
# -------- 제곱수 1개 --------
s = int(math.sqrt(n))
if s * s == n or (s + 1) * (s + 1) == n:
return 1
4개인 경우는 4를 인수로 가지지 않을때까지 나눈 후 이를 모듈로 연산을 해 비교를 했다.
# -------- 제곱수 4개 --------
while n4 % 4 == 0:
n4 //= 4
if n4 % 8 == 7:
return 4
3은 위의 경우들이 통과되지 않을 때 이므로 마지막에 달아두었다.
문제는 2개인 경우이다.
이를 해결하기 위해서 폴라드로와 밀러라빈이 필요했다. 그래서 BOJ 13926에서 썼던 코드를 재활용하기로 했다. 또한 N의 값이 너무 크므로 일단 10**5 이하의 작은 소수들은 에라토스테네스의 체로 구한 소수로 미리 인수분해를 시켜둔 뒤 최대한 폴라드 로와 밀러 라빈에 가해지는 부담을 줄이는 방법을 활용했다.
그리고 그렇게 얻은 소수 dict들을 이용해 해당 key,value값을 얻어가며 key mod 4가 3을 만족할 때 value의 odd,even여부를 판단해 2개인지를 판별하는 코드를 작성했다.
# -------- 제곱수 2개 --------
primes = defaultdict(int)
def PrimeList(num): # 작은 소수 미리 쳐내기
prime_array = [True] * (num + 2)
prime_array[0] = prime_array[1] = False
pr = []
for i in range(2, num + 2):
if prime_array[i]:
pr.append(i)
for j in range(i * i, num + 2, i):
prime_array[j] = False
return pr
pList = PrimeList(10**5)
temp_n = n
for p in pList:
while temp_n % p == 0:
primes[p] += 1
temp_n //= p
n = temp_n
def PollardRho(n):
def F(x, c): return (x * x + c) % n
if n % 2 == 0:
return 2
c = randint(1, 10)
x, y, d = 2, 2, 1
while d == 1:
x = F(x, c)
y = F(F(y, c), c)
d = math.gcd(abs(x - y), n)
if d == n:
c = randint(1, 10)
x, y, d = 2, 2, 1
if d != 1 and d != n:
return d
return None
def MillerRabin(n):
if n < 2:
return False
if n % 2 == 0:
return n == 2
r, s = 0, n - 1
while s % 2 == 0:
r += 1
s //= 2
for _ in range(10):
a = randint(2, n - 1)
x = pow(a, s, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
def recursion(n):
if n == 1:
return
if MillerRabin(n):
primes[n] += 1
return
d = PollardRho(n)
if d is None or d == 1 or d == n:
primes[n] += 1
return
recursion(d)
recursion(n // d)
recursion(n)
two = True
for p, e in primes.items():
if p % 4 == 3 and (e & 1):
two = False
break
if two and primes:
return 2
이를 합쳐서 완성 코드를 만들었다.
from collections import defaultdict
from random import randint
import math,sys
sys.setrecursionlimit(10**5)
def Run(n):
n4 = n
# -------- 제곱수 1개 --------
s = int(math.sqrt(n))
if s * s == n or (s + 1) * (s + 1) == n:
return 1
# -------- 제곱수 2개 --------
primes = defaultdict(int)
def PrimeList(num): # 작은 소수 미리 쳐내기
prime_array = [True] * (num + 2)
prime_array[0] = prime_array[1] = False
pr = []
for i in range(2, num + 2):
if prime_array[i]:
pr.append(i)
for j in range(i * i, num + 2, i):
prime_array[j] = False
return pr
pList = PrimeList(10**5)
temp_n = n
for p in pList:
while temp_n % p == 0:
primes[p] += 1
temp_n //= p
n = temp_n
def PollardRho(n):
def F(x, c): return (x * x + c) % n
if n % 2 == 0:
return 2
c = randint(1, 10)
x, y, d = 2, 2, 1
while d == 1:
x = F(x, c)
y = F(F(y, c), c)
d = math.gcd(abs(x - y), n)
if d == n:
c = randint(1, 10)
x, y, d = 2, 2, 1
if d != 1 and d != n:
return d
return None
def MillerRabin(n):
if n < 2:
return False
if n % 2 == 0:
return n == 2
r, s = 0, n - 1
while s % 2 == 0:
r += 1
s //= 2
for _ in range(10):
a = randint(2, n - 1)
x = pow(a, s, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
def recursion(n):
if n == 1:
return
if MillerRabin(n):
primes[n] += 1
return
d = PollardRho(n)
if d is None or d == 1 or d == n:
primes[n] += 1
return
recursion(d)
recursion(n // d)
recursion(n)
two = True
for p, e in primes.items():
if p % 4 == 3 and (e & 1):
two = False
break
if two and primes:
return 2
# -------- 제곱수 4개 --------
while n4 % 4 == 0:
n4 //= 4
if n4 % 8 == 7:
return 4
# -------- 제곱수 3개 --------
return 3
N = int(input())
print(Run(N))
개인적으로 BOJ 13926과 결이 비슷했으나 이 발상이 떠올리기 매우 어려우며 배경지식이 많이 필요해 어려웠던 문제였다.
실제로 코드를 짜는 시간은 2시간도 채 안됐으나 이를 해결하기 위해 공부하는 시간이 거의 4시간 가까이 됐었다.
그냥 이런 개념도 있구나 라고 학습하기 좋은 문제였던거 같다.
'백준' 카테고리의 다른 글
| BOJ 1786 찾기 (0) | 2025.04.03 |
|---|---|
| BOJ 1708 볼록 껍질 (0) | 2025.04.01 |
| BOJ 2357 최솟값과 최댓값 (0) | 2025.04.01 |
| BOJ 13926 gcd(n, k) = 1 (0) | 2025.03.31 |