약수와 배수

약수와 배수란?

\(a\)를 \(b\)로 나누어 떨어지면(\(a \% b == 0\)), \(b\)는 \(a\)의 약수, \(a\)는 \(b\)의
배수입니다. 이 관계와 최대공약수(GCD)·최소공배수(LCM)는 정수론 문제의 기본기입니다.

1. 약수 구하기

\(N\)의 약수를 찾으려면 1부터 \(N\)까지 나눠 보면 되지만, 더 빠른 방법이 있습니다.

int n; cin >> n;
for (int i = 1; i <= n; i++)
    if (n % i == 0) cout << i << ' ';   // i가 약수

약수는 항상 쌍으로 나옵니다. \(i\)가 약수면 \(N/i\)도 약수죠. 그래서 \(\sqrt{N}\)까지만
보면 됩니다(아래 구현 단원에서 다룸).

2. 최대공약수 (GCD)

두 수의 공통 약수 중 가장 큰 것입니다. 유클리드 호제법으로 빠르게 구합니다.

\(\gcd(a, b) = \gcd(b, a \bmod b)\), 그리고 \(\gcd(a, 0) = a\)

"큰 수를 작은 수로 나눈 나머지로 바꾸기"를 나머지가 0이 될 때까지 반복합니다.

gcd(24, 18)
= gcd(18, 24%18=6)
= gcd(6, 18%6=0)
= 6

이 방법은 \(O(\log)\) 수준으로 매우 빠릅니다. 1부터 다 나눠 보는 것과 비교가 안 됩니다.

3. 최소공배수 (LCM)

두 수의 공통 배수 중 가장 작은 것. GCD를 이용한 공식이 있습니다.

$$ \text{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)} $$

long long lcm = (long long)a / gcd(a, b) * b;   // 곱 전에 나눠서 오버플로 방지

\(a \times b\)가 클 수 있으니, 먼저 나누고 곱하는 순서가 안전합니다.

4. 자주 쓰는 곳

• 분수 약분(분자·분모를 GCD로 나눔).
• "동시에 출발한 두 신호가 다시 만나는 시각" → LCM.
• "여러 개를 똑같이 나눠 담는 최대 크기" → GCD.

복잡도

• 약수 나열(단순): \(O(N)\), \(\sqrt N\) 기법: \(O(\sqrt N)\).
• 유클리드 호제법: \(O(\log \min(a,b))\).

정리

• 약수/배수는 % == 0으로 판정.
• GCD는 유클리드 호제법: \(\gcd(a,b)=\gcd(b, a\%b)\).
• LCM은 \(a \times b / \gcd(a,b)\) — 곱 전에 나누기.
• 약분, 주기, 균등 분배 문제의 기본 도구.

약수와 배수 구현 레퍼런스

약수 빠르게 세기, GCD/LCM 구현, 그리고 실전 적용을 코드로 정리합니다.

1. 약수를 √N까지만 구하기

int n; cin >> n;
vector<int> divs;
for (int i = 1; (long long)i * i <= n; i++) {
    if (n % i == 0) {
        divs.push_back(i);
        if (i != n / i) divs.push_back(n / i);  // 짝꿍 약수
    }
}
cout << divs.size() << '\n';   // 약수의 개수

n = int(input())
divs = set()
i = 1
while i * i <= n:
    if n % i == 0:
        divs.add(i)
        divs.add(n // i)
    i += 1
print(len(divs))

i와 n/i가 같을 때(제곱수의 가운데 약수)는 한 번만 세야 하므로 i != n/i 검사가
필요합니다. 이 기법으로 \(O(N)\)이 \(O(\sqrt N)\)으로 줄어듭니다.

2. 유클리드 호제법 (GCD)

int gcd(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}
// C++17 이상이면 std::__gcd(a,b) 또는 <numeric>의 gcd(a,b)도 가능

import math
print(math.gcd(a, b))   # 파이썬은 내장
# 직접 구현:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

3. LCM과 실전 적용

long long lcm = (long long)a / gcd(a, b) * b;

예: "분수 a/b를 기약분수로" — 분자·분모를 GCD로 나눕니다.

int g = gcd(a, b);
cout << a / g << '/' << b / g << '\n';

4. 함정과 패턴 인식

• LCM 오버플로 — a * b를 먼저 하면 넘침. a / gcd * b 순서로.
• 0 처리 — gcd(a, 0) = a. b가 0이면 나누기 금지(호제법은 자연히 처리됨).
• √N 중복 — 제곱수에서 가운데 약수 두 번 세지 않기.
• 약수 정렬 — n/i로 큰 약수를 함께 넣으면 순서가 섞이니, 필요하면 정렬.

문제에 "약수의 개수/합", "최대공약수/최소공배수", "기약분수", "동시에 만나는",
"똑같이 나눠" 같은 말이 보이면 이 단원입니다.

정리

핵심은 (1) 약수는 \(\sqrt N\)까지 + 짝꿍, (2) GCD는 유클리드 호제법(또는 내장),
(3) LCM은 a / gcd * b로 오버플로 회피입니다. GCD/LCM 함수는 통째로 외워 두면
정수론 문제에서 두고두고 씁니다.