[정수론] 약수, 배수, 최대공약수, 최소공배수와 관련된 알고리즘

 

공약수와 최대공약수(GCD),  공배수와 최소공배수(LCM), 유클리드의 호제법 (Euclidean Algorithm)

나눗셈 정리 (Division Algorithm)

임의의 정수 $a, b\ (b \neq 0)$에 대하여 $a = bq + r$, $0 \le r < |b|$를 만족하는 정수 $q, r$가 유일하게 존재한다. 이때 $q$는 몫(quotient)라 하고, $r$는 나머지(remainder)라 한다.

 

파이썬 코드에서는 간단히 구할 수 있다.

q = a // b
r = a % b

 

약수와 배수 (divisor and multiple)

두 정수 $a, b \ (b \neq 0)$에 대하여 $b=ac$를 만족하는 정수 $c$가 존재할 때, $b$를 $a$의 배수(multiple)라 하고 $a$를 $b$의 약수(divisor) 또는 인수(factor)라 한다. 
이때 "$a$는 $b$를 나눈다" 또는 "$b$는 $a$에 의하여 나누어떨어진다" 라고 하고, $a \mid b$로 표시한다.
$a$가 $b$를 나누지 않으면 $a \nmid b$로 표시한다.

 

파이썬에서 약수와 배수는 다음과 같이 구할 수 있다.

if b % a == 0:
    print(f"{a} is a divisor of {b}.")
    print(f"{b} is a multiple of {a}.")
else:
    print(f"{a} is not a divisor of {b}.")
    print(f"{b} is not a multiple of {a}.")

 

관련문제: BOJ 17425, 약수의 합

사실 에라토스테네스의 체를 살짝 응용해서 풀 수 있다.

그렇지만 약수를 구할 때, $\sqrt{n}$까지만 탐색해서 구할 수 있다는 아이디어를 이용할 수 있다.

참고로, python은 어떻게 해도 시간초과가 나서 Pypy3로 제출하여 통과하였다.

에라토스테네스의 체와 달리, 모든 수에서 약수를 구한다.

단, 1과 자기 자신은 항상 더해야하므로 후처리 누적합 단계에서 같이 더해주었다.

import sys
#sys.stdin = open('input.txt', 'r')
#sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

MAX = 1000000
g = [0 for i in range(MAX + 1)]
i = 2
while i * i <= MAX:
    for j in range(i * i, MAX + 1, i):
        g[j] += i
        if i != j // i:
            g[j] += j // i
    i += 1
    
g[1] = 1  
for i in range(2, MAX + 1):
    g[i] += i + 1 + g[i - 1]
    
T = int(input())
for _ in range(T):
    N = int(input())
    print(g[N])

 

혹은 직관적으로 dp[i * j]를 계산할 수 있다.

$i$를 약수로 갖는 모든 수(즉, $i$의 배수들) $i \times j$에 $i$를 더하는 것이다.

import sys
#sys.stdin = open('input.txt', 'r')
#sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

MAX = 10 ** 6
dp = [0] * (MAX + 1)
for i in range(1, MAX + 1):
    j = 1
    while i * j <= MAX:
        dp[i * j] += i
        j += 1
    dp[i] += dp[i - 1]
    
T = int(input())
for _ in range(T):
    N = int(input())
    print(dp[N])

 

공약수(common divisor)와 최대공약수(Greatest Common Divisor; GCD)

$a, b \in \mathbb{Z}$라 하자. 양의 정수 $d$가 다음 두 조건
(1) $d \mid a$ and $d \mid b$
(2) if $c \mid a$ and $c \mid b$, then $c \le d$
을 만족하면 최대공약수(greatest common divisor)라고 한다. 조건 (1)만 만족하면 공약수(common divisor)이다.

이를 일반화하면 다음과 같다.
$a_1, a_2, \dots, a_n \in \mathbb{Z}$과 $d \in \mathbb{Z} (d \neq 0)$에 대하여 
(1) $d \mid a_i (1 \le i \le n) $
(2) $c \in \mathbb{Z}$이고 $c \mid a_i \ (1 \le i \le n)$이면 $c \mid d$이다.
조건 (1)만을 만족하는 $d$를 공약수라하고, 조건 (1)과 (2) 모두 만족하는 양의 정수 $d$를 최대공약수라고 한다.

 

여기서 최대공약수는 $d=\gcd(a, b)$ 또는 $(a_1, a_2, \dots, a_n)$으로 나타낸다.

예를 들어 $\gcd(-12, 30)=6$ 또는 간단히 $(30, -12)=6$으로 나타낸다.

 

유클리드의 호제법: 최대공약수를 찾는 방법 (Euclidean Algorithm)

모두는 $0$이 아닌 두 정수 $a, b$ 사이에 $a = bq + c$인 관계가 성립한다고 하자. $a$와 $b$의 공약수 전제 집합을 $A$라 하고, $b$와 $c$의 공약수 전제 집합을 $B$라 하면 $A=B$이다.
특히, $(a, b) = (b, c)$이다.

위 정리를 나눗셈 정리를 반복 적용하면 다음을 구할 수 있다.

\begin{align} a &= q_{1} b + r_{1}, \qquad 0 < r_{1} < b \\ b &= q_{2} r_{1} + r_{2}, \qquad 0 < r_{2} < r_{1} \\ r_1 &= q_{3} r_{2} + r_{3}, \qquad 0 < r_{3} < r_{2} \\ \vdots \\ r_{n-2} &= q_{n} r_{n-1} + r_n, \qquad 0 < r_n < r_{n-1} \\ r_{n-1} &= q_{n+1} r_n + 0. \end{align}

나눗셈 정리를 반복 적용하다보면 나머지가 $0$인 지점이 반드시 생긴다.

왜냐하면 $r_1 > r_2 > r_3 > \cdots \ge 0$이므로 무한히 계속할 수는 없기 때문이다.

 

다시 위 정리를 이용하면 

\[ (a, b) = (b, r_1) = (r_1, r_2) = \cdots = (r_{n-1}, r_{n}) = r_{n} \]

임을 얻을 수 있다.

 

파이썬 코드는 다음과 같다.

시간복잡도는 $O(\log \min(a, b))$이다.

시간복잡도 증명은 생각보다 까다로운데, 피보나치 수열과 수학적 귀납법을 이용하여 증명한다.

https://www.geeksforgeeks.org/time-complexity-of-euclidean-algorithm/

Time Complexity of Euclidean Algorithm - GeeksforGeeks

 

# using math package
import math
d = math.gcd(a, b)
d = math.gcd(a, b, c) # more than two numbers are available
d = math.gcd()  # 0
d = math.gcd(0) # 0
d = math.gcd(a) # a

# by own, only two integers
# assume a > b
def my_gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

 

여러 정수의 최대공약수는 다음과 같이 구한다.

$a_1, a_2, \dots, a_n \in \mathbb{Z} \ (n \ge 2)$라 하자.
$a_1, a_2, \dots, a_n$이 모두는 $0$이 아닐 때,
\[ (a_1, a_2, \dots, a_n) = ((a_1, a_2, \dots, a_{n-1}), a_n) \]
이다.

예를 들어, $(84, 72, 102) = ((84, 72), 102) = (12, 102) = 6$ 이다.

 

관련 문제: BOJ 2485, 가로수

직선 도로에 불균일하게 나무가 심어져 있는데, 추가로 나무를 심어서 균등간격으로 만든다.

처음에 심어진 가로수들의 간격들의 gcd를 구한다. 

이때 $(a_1, a_2, \dots, a_n) = ((a_1, a_2, \dots a_{n-1}), a_n)$을 이용한다.

그렇게 구한 (새로운 간격일 때 심어야하는 가로수의 수) - (이미 심어진 나무 수)를 계산한다.

import sys
#sys.stdin = open('input.txt', 'r')
input = sys.stdin.readline

def my_gcd(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a

N = int(input())
arr = [0] * N
numbers = [0] * (N - 1)
for i in range(N):
    arr[i] = int(input())

for i in range(N - 1):
    numbers[i] = arr[i + 1] - arr[i]

gcd = my_gcd(numbers[0], numbers[1])
for num in numbers[2:]:
    gcd = my_gcd(gcd, num)

answer = (arr[-1] - arr[0]) // gcd - len(arr) + 1
print(answer)

 

공배수(common multiple)와 최소공배수(The Least Common Multiple; LCM)

 

$a, b \in \mathbb{Z}$라 하자. 양의 정수 $l$가 다음 두 조건
(1) $a \mid l$ and $b \mid l$
(2) if $a \mid c$ and $b \mid c$, then $l \le c$
을 만족하면 최소공배수(least common multiple)라고 한다. 조건 (1)만 만족하면 공배수(common multiple)이다.

이를 일반화하면 다음과 같다.
$a_1, a_2, \dots, a_n \in \mathbb{Z}$과 $l \in \mathbb{Z} (l \neq 0)$에 대하여 
(1) $a_i \mid al (1 \le i \le n) $
(2) $l \neq 0$이고 $a_i \mid b \ (1 \le i \le n)$이면 $l \mid b$이다.
조건 (1)만을 만족하는 $l$를 공배수라하고, 조건 (1)과 (2) 모두 만족하는 양의 정수 $d$를 최소공배수라고 한다.

 

여기서 공배수는 $\text{lcm}(a, b)$또는 $[a, b]$로 표기한다.

$a_1, a_2, \dots, a_n \in \mathbb{Z} \ (n \ge 2)$라 하자.
$a_1, a_2, \dots, a_n$이 모두는 $0$이 아닐 때,
\[ [a_1, a_2, \dots, a_n] = [[a_1, a_2, \dots, a_{n-1}], a_n] \]
이다.

 

예를 들어, $[6, 8, 10] = [[6, 8], 10] = [24, 10] = 120$이다.

# using math package
import math
l = math.lcm(a, b)
l = math.lcm(a, b, c) # more than two numbers are available
l = math.lcm()  # 0
l = math.lcm(0) # 0
l = math.lcm(a) # a

# by own, only two integers
# assume a > b
def get_gcd(a, b):
    if a < b:
        a, b = b, a
        
    while b != 0:
        a, b = b, a % b
        
    return a

def get_lcm(a, b):
    g = get_gcd(a, b)
    return (a * b) // g

 

 

최대공약수와 최소공배수와의 관계

$a, b$를 모두 $0$이 아닌 정수라 하자. 그러면 $a, b$의 최대공약수와 최소공배수를 $(a, b)$, $[a, b]$에 대하여 다음이 성립한다.
\[ (a, b) [a, b] = |ab| \]
또는
\[ \gcd(a, b) \text{lcm}(a, b) = |ab| \]

그러나 3개 이상의 정수에 대해서는 성립하지 않는다.

$[6, 8, 10]=120$이고 $(6, 8, 10) = 2$이지만 $6 \cdot 8 \cdot 10 = 480$이다.

즉 $(6, 8, 10) [6, 8, 10] \neq 6 \cdot 8 \cdot 10$ 이다.

 

관련 알고리즘 문제: BOJ 1735, 분수 합

https://www.acmicpc.net/problem/1735

분모를 통분할 때, 최소공배수가 필요하다.

그리고 최소공배수는 최대공약수를 통해 계산할 수 있다.

최종적으로 통분한 분수식이 기약분수로 만들기 위해서 분자와 분모의 최대공약수로 나누어준다.

def get_gcd(a, b):
    if a < b:
        a, b = b, a
        
    while b != 0:
        a, b = b, a % b
        
    return a

def get_lcm(a, b):
    g = get_gcd(a, b)
    return (a * b) // g

a1, b1 = map(int, input().split())
a2, b2 = map(int, input().split())

b3 = get_lcm(b1, b2)
m1, m2 = b3 // b1, b3 // b2
a3 = (a1 * m1) + (a2 * m2)
g = get_gcd(a3, b3)
print(a3 // g, b3 // g)