백준 17633: 제곱수의 합 (More Huge)

※이전 블로그에서 가져온 글입니다※

---

[Diamond III] 제곱수의 합 (More Huge) - 17633

문제 링크

성능 요약

메모리: 39912 KB, 시간: 184 ms

분류

수학, 밀러–라빈 소수 판별법, 정수론, 폴라드 로, 소수 판정

제출 일자

2023년 11월 23일 09:55:59

문제 설명

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 1252 + 62 + 12 + 12라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 1052 + 152 + 82 + 52.

자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 1,000,000,000,000,000,000이다.

출력

출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.

---

어떤 자연수 $n$이 주어질 때, 이 자연수를 나타낼 수 있는 제곱수 합의 최소 개수를 출력하는 문제입니다. 문제에서 최대 개수는 4개로 주어져있기에, 1부터 4까지의 경우에 대해 생각해보면 됩니다.

르장드르의 세 제곱수 정리

르장드르의 세 제곱수 정리란, $n=4a(8b+7)$일 때 3개의 자연수의 합으로 나타낼 수 없다라는 정리입니다. 따라서, $n$의 형태가 $4a(8b+7)$이라면 4개로 나타낼 수 있으므로 4를 출력하면 됩니다.

def legendre(n):
    while n%4 == 0:
        n //= 4
    if n%8 == 7: return True
    else: return False

페르마의 두 제곱수 정리

페르마의 두 제곱수 정리 중 한 조건에 따르면, 소인수 중 4로 나눈 나머지가 3인 소인수가 홀수 개라면 두 제곱수의 합으로 나타낼 수 없습니다. 따라서 $n$을 소인수분해하고, $4n+3$ 형태의 소수가 홀수 개라면 3을 출력하면 됩니다.

def fermat(n):
    lists = []
    while n > 1:
        soinsu = pollardRho(n)
        lists.append(soinsu)
        n //= soinsu
    k = list(Counter(lists).items())
    for i, n in k:
        if i%4 == 3 and n%2 == 1:
            return True
    return False

제곱수

주어진 자연수가 제곱수라면, 1개의 제곱수(자기 자신)로 나타낼 수 있으므로 1을 출력하면 됩니다. 그게 아니라면 2를 출력하면 됩니다.