1. 소수(prime number)의 기초적인 상식
소수(prime number)는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수입니다.
2를 제외한 모든 소수는 2로 나누어 떨어지지 않기 때문에 홀수입니다.
2보다 큰 임의의 소수를 p라고 했을 때, p ≡ 1(mod 2)(2에 대한 나머지가 1)입니다.
그리고 홀수인 소수(2를 제외한 소수)는 4로 나누어 떨어지지 않습니다.
따라서 홀수인 소수 p ≡ 1(mod 4)(4에 대한 나머지가 1) 또는 p ≡ 3(mod 4)(4에 대한 나머지가 3)입니다.
2. 페르마의 두 제곱수 정리
홀수인 소수(2를 제외한 소수)가 두 개의 제곱수의 합이 될 필요충분조건이 p ≡ 1(mod 4)라는 정리입니다.
반대로 말하면 홀수인 임의의 소수가 4로 나누었을 때 나머지가 1이라면 그 수는 두 제곱수의 합으로 나타낼 수 있다는 것입니다.
예를 들어, 4로 나누었을 때 나머지가 1인 소수는 5, 13, 17, 29 등입니다.
이 소수들은 각각 \(5 = 1^2 + 2^2\), \(13 = 2^2 + 3^3\), \(17 = 1^2 + 4^2\), \(29 = 2^2 + 5^2\) 로 나타낼 수 있습니다.
이제 소수를 정수 범위로 확장시켜봅시다. 이때는 해당 정수를 소인수분해 해서 소인수 중에 4로 나누었을 때 나머지가 3인 소수의 개수가 짝수이면 두 제곱수의 합으로 나타낼 수 있습니다. 증명은 다음과 같습니다.
먼저 두 제곱수의 합으로 나타낼 수 있는 두 수의 곱도 두 제곱수의 합으로 나타낼 수 있습니다.
식으로 나타내면 \((a^2 + b^2) \times (c^2 + d^2)\) 도 두 제곱수의 합으로 나타낼 수 있다는 것입니다.
증명은 어렵지 않은데, 위 식을 풀어쓰면
\(a^2c^2 + a^2d^2 + b^2c^2 + b^2d^2\)으로 나타낼 수 있습니다.
또 이 식은,
\((a^2c^2 + 2abcd + b^2d^2) + (a^2d^2 -2abcd + b^2c^2)\)으로 쓸 수 있고, 정리하면
\( (ac+bd)^2 + (ad-bc)^2 \)가 되므로, 두 제곱수의 합이 됩니다.
다음으로 2는 \(1^2 + 1^2)\)으로 두 제곱수의 합으로 나타낼 수 있으며, \(4^n = (2^2)^n = (2^n)^2\)이므로 소인수 중 2가 몇 개가 되더라도 두 제곱수의 합으로 나타낼 수 있습니다.
따라서 두 제곱수의 합으로 나타낼 수 있는지 영향을 주는 소인수는 4로 나누었을 때 나머지가 3인 소수 뿐이며, 해당 소수가 짝수 개이면 완전제곱수로 나타낼 수 있으므로, 결국 홀수 개일 때 두 제곱수의 합으로 나타낼 수 없게 됩니다.
https://ko.wikipedia.org/wiki/페르마_두_제곱수_정리
페르마 두 제곱수 정리 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 수론에서 페르마 두 제곱수 정리(-數定理, 영어: Fermat's theorem on sums of two squares)는 홀수 소수가 두 개의 제곱수의 합일 필요 충분 조건이 4에 대한 나머지가 1이
ko.wikipedia.org
3. 르장드르의 세 제곱수 정리
자연수 n이 세 개 이하의 제곱수의 합이 될 필요충분조건이 \(\mathbf{n \neq 4^a(8b+7)}\)(a, b는 음이 아닌 정수)라는 정리입니다.
다시 말해 어떤 자연수를 세 개 이하의 제곱수의 합으로 표현하려면 4로 나누어 떨어지지 않으면서, 8로 나누었을 때 나머지가 7이 아니어야 한다는 것을 알 수 있습니다.
반대로 말하면 4로 나누어 떨어지지 않을 때까지 나눈 후 8로 나누었을 때 나머지가 7이면 세 개 이하의 제곱수의 합으로 표현할 수 없다는 것입니다.
이후 라그랑주의 네 제곱수의 정리에 의해서 세 개 이하의 제곱수로 나타내지 못하면 반드시 네 개의 제곱수로 나타낼 수 있습니다.
위의 두 제곱수 정리는 소수와 관련된 반면, 세 제곱수 정리는 자연수 범위입니다.
따라서 세 개의 제곱수에는 \(0^2\)도 가능합니다.
예를 들어 두 제곱수에서 살펴본 수 5는 \(5 = 0^2 + 1^2 + 2^2\)으로 세 제곱으로 나타낼 수 있습니다.
https://en.wikipedia.org/wiki/Legendre's_three-square_theorem
Legendre's three-square theorem - Wikipedia
From Wikipedia, the free encyclopedia Says when a natural number can be represented as the sum of three squares of integers In mathematics, Legendre's three-square theorem states that a natural number can be represented as the sum of three squares of integ
en.wikipedia.org
4. 라그랑주의 네 제곱수 정리
모든 양의 정수는 많아도 네 개의 제곱수의 합이라는 정리입니다.
쉽게 생각해서 모든 자연수는 0을 포함하여 네 개의 제곱수로 나타낼 수 있다는 말과 같습니다.
https://ko.wikipedia.org/wiki/라그랑주_네_제곱수_정리
라그랑주 네 제곱수 정리 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 수론에서 라그랑주 네 제곱수 정리(-數定理, 영어: Lagrange's four-square theorem)는 모든 양의 정수가 많아야 4개의 제곱수의 합이라는 정리이다.[1] 양의 정수 n ∈ Z +
ko.wikipedia.org
5. 문제에 적용
가. 제곱수의 합
https://www.acmicpc.net/problem/1699
임의의 자연수 N이 주어졌을 때, N을 제곱수의 합으로 표현할 때 항의 최소 개수를 구하는 문제입니다.
N의 범위는 10만 이하이고, 시간 제한은 2초입니다.
범위가 작고, 시간이 꽤 넉넉한 편입니다.
그리고 이 문제의 분류는 다이나믹프로그래밍입니다.
따라서 굳이 위에서 살펴본 제곱수 정리들을 사용하지 않아도 충분히 해결이 가능합니다.
핵심 아이디어는 다음과 같습니다.
N이 제곱수 한 개의 항으로 나타낼 수 있을 때는 N이 제곱수 자체일 때입니다.
dp테이블의 i번째 요소는 i를 제곱수의 합으로 표현할 때 항의 최소 개수로 설정합니다.
점화식을 만들면, dp[i] = min(dp[i], dp[j1] + dp[i-j1], dp[j2] + dp[i-j2], ...)입니다.
이때 j는 i보다 작은 제곱수들입니다.
제곱수는 항의 최소 개수가 1이므로, dp[i] = min(dp[i], 1 + dp[i-j1], 1 + dp[i-j2], ...) 가 됩니다.
dp = [4]*(N+1)
for i in range(1, N+1):
if (i**0.5)%1 == 0:
dp[i] = 1
j = 1
while j*j <= i:
dp[i] = min(dp[i], 1+dp[i-j*j])
j += 1
나. Four Squares
https://www.acmicpc.net/problem/17626
이전 문제와 같은 문제입니다.
하지만 N의 범위가 5만 이하이고, 시간 제한은 0.5초입니다.
시간이 좀 빡빡해졌지만, 범위가 작기 때문에 위 문제와 같이 DP로 풀 수 있습니다.
하지만 본문에서 공부한 제곱수 정리를 통해 풀어봅시다.
먼저 주어진 수가 완전제곱수라면 1을 출력합니다.
if (N**0.5)%1 == 0:
return 1다음으로 소인수분해하여 4로 나누었을 때 나머지가 3인 소수가 홀수 개인지 확인합니다.
모두 짝수 개라면 2를 출력합니다.
소인수분해를 하기 위해 5만보다 작은 소수들을 미리 찾아서 정리합니다.
(소수는 에라토스테네스의 체 알고리즘을 사용하여 찾았습니다.)
p = [False, False] + [True] * 49999
for i in range(2, 50001):
if p[i]:
for j in range(2*i, 50001, i):
p[j] = False
n = N
for i in range(2, 50001):
if i:
cnt = 0
while n % i == 0:
n //= i
cnt += 1
if i%4 == 3 and cnt%2 == 1:
break
else:
return 2마지막으로 4로 나누어지지 않을 때까지 나눈 후, 8로 나누었을 때 나머지가 7이 아니면 3을 출력, 나머지가 7이면 4를 출력합니다.
while N % 4 == 0:
N //= 4
if N%8 != 7:
return 3
return 4
다. 라그랑주의 네 제곱수 정리
https://www.acmicpc.net/problem/3933
2^15 보다 작은 자연수가 주어졌을 때, 항의 개수가 4를 넘지 않으면서 제곱수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제입니다.
예를 들어 4의 경우, 2^2으로 최소 항의 개수는 1이지만, 이번 문제는 1^2 + 1^2 + 1^2 + 1^2 도 가능하므로 자연수 4의 답은 2가 됩니다.
제곱수의 합으로 나타낼 수 있는 최소 항의 개수를 구하는 문제가 아니므로 다른 아이디어가 필요합니다.
2^15 = 32768로 크지 않고, 항의 개수는 최대 4개이므로, 32768 * 4 크기의 dp 테이블로 해결할 수 있을 것 같습니다.
dp[i][j]에 입력할 값은 자연수 i를 제곱수 항의 개수 j개로 나타낼 수 있는 경우의 수로 정합니다.
이전 문제와 마찬가지로, 항의 개수가 1개인 경우는 주어진 자연수가 제곱수인 경우입니다.
i가 제곱수라면 dp[i][1] = 1이 됩니다.
특정 제곱수를 찾은 다음으로 32768 범위 안에서 dp[k][j] 에 dp[k - i][j-1]의 값을 추가해주면서 dp 테이블을 수정합니다.
주어진 범위 안에서 계속해서 제곱수를 찾아가면서 위 과정을 반복하면 해당 범위 내의 모든 경우를 다 찾을 수 있습니다.
표를 그려 확인하면, 첫번째 제곱수가 1이므로 (1, 1)에 1을 입력합니다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
그 다음 주어진 범위 내에서 dp[k][j]에 dp[k-1][j-1] 값을 더해줍니다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
이 dp테이블의 의미는 제곱수 1을 가지고 표현했을 때, 1, 2, 3, 4가 각각 1개(1^2), 2개(1^2 + 1^2), 3개(1^2 + 1^2 + 1^2), 4개(1^2 + 1^2 + 1^2 + 1^2)의 항을 가진다는 의미입니다.
이제 다음 제곱수는 4이므로 (4, 1)에 1을 입력합니다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
그 다음 주어진 범위 내에서 dp[k][j]에 dp[k-4][j-1] 값을 더해줍니다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 3 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 4 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
표에서 5, 6, 7에 추가된 값은 각각 1, 2, 3의 값에서 나온 값입니다.
따라서 의미를 생각해보면, 5, 6, 7의 값은 각각 2개(1^2 + 2^2), 3개(1^2 + 1^2 + 2^2), 4개(1^2 + 1^2 + 1^2 + 2^2)의 항을 가진다는 뜻입니다.
그리고 8, 9에 추가된 값은 각각 4, 5의 값에서 나온 값이므로 각각 2개(2^2 + 2^2), 3개(1^2 + 2^2 + 2^2)의 항을 가진다는 뜻입니다.
이런 식으로 범위 안의 모든 제곱수에서 이 작업을 반복하면, 모든 경우를 전부 찾을 수 있습니다.(브루트포스)
n = 2**15
dp = [[0]*4 for _ in range(n)]
i = 1
while i*i < n:
dp[i*i][0] = 1
for j in range(i*i+1, n):
dp[j][1] += dp[j-i*i][0]
dp[j][2] += dp[j-i*i][1]
dp[j][3] += dp[j-i*i][2]
i += 1
라. 한 발(아니면 훨씬) 더 나아가야 풀 수 있는 문제
다섯 제곱수의 합
https://www.acmicpc.net/problem/28383
가장 적은 수의 제곱수의 합으로 나타내는 것이 아니라 네 제곱수의 합, 다섯 제곱수의 합으로 나타낼 수 있는 경우의 수를 찾는 문제입니다.
제곱수
https://www.acmicpc.net/problem/23287
이 문제는 제곱수의 합으로 나타낼 때 항이 몇 개인지가 아니라, 네 제곱수의 합으로 나타낼 때 각 항을 구하는 문제입니다.
제곱수의 합(More Huge)
https://www.acmicpc.net/problem/17633
풀어본 문제와 완벽히 같은 문제이지만, N의 범위가 1,000,000,000,000,000,000으로 매우 큽니다. 두 제곱수의 합으로 나타낼 수 있는지 확인하기 위한 소인수분해에서 또 다른 아이디어가 필요한 문제입니다.
제곱수의 합 2(More Huge)
https://www.acmicpc.net/problem/17646
위 문제와 완벽히 같지만, 각 항을 구해야하는 문제입니다. 난이도가 심상치 않습니다.
