N보다 작은 특정 수의 배수를 찾아보자[최대 공약수, 최소 공배수, 교집합, Ugly Number III]

## 접근방법

---

간단히 생각해보자, N보다 작은 2의 배수의 개수는 몇 개일까? 정답은, N / 2개이다. N / 2개가 된다는 사실은 자명하므로 증명은 생략하겠다.

 

 

 

A와 B가 있을 때, 두 수의 최대 공약수는 얼마일까? GCD(A, B) = GCD(B, A % B)이다. 증명은 아래와 같다.
GCD(A, B) = G일 때, GCD(B, A % B)의 최대공약수도 G일까?

 

 

 

A = G * a

B = G * b

 

 

A = B * q + r 

A % B = r = A - B * q

 

 

 

B = G * b

r = A -  B * q = G * a - G * b * q= G(a - bq)

 

 

 

으로 증명될 수 있다. 이제 최소 공배수에 대해서 알아보자, 최소 공배수는 두 수의 곱에다가 최대 공약수를 나눠주면 된다. 

LCM(A, B) = A * B / GCD(A, B)

 

 

 

지금까지, 두 수에 최대 공약수와 최소 공배수만 다뤘었다, 만약에 최대 공약수나 최소 공배수를 3개 이상의 수에 대해서 구해야 한다면 어떻게 해야 할까? 즉, 결합법칙이 성립할까? 성립하지 않을까? 정답은 성립한다.

 

 

 

GCD(A, B, C) = GCD(GCD(A, B), C) = GCD(A, GCD(B, C))가 성립함을 기억해두자.

 

 

 

자 이제, 문제의 첫 질문으로 돌아가보자. N보다 작은 K의 배수가 몇개인지 확인하고 싶었다. 근데 왜 최대 공약수, 최소 공배수 개념이 필요했을까? 구하고자 하는 배수가 여러개라고 생각해보자. A, B, C의 배수에 대해서 확인하고 싶다면, 어떻게 해야할까?

 

 

 

최소 공배수와 최대 공약수의 개념을 이용해서, 겹치는 수들을 모두 제거해야 정확한 개수를 파악할 수 있다. 겹치는 수들을 제거하는 것이 핵심이다. 2개의 수라면, 간단히 최소 공배수들만 제거해주면 되지만, 3개 이상의 수라면 집합 관계를 떠올리자.

 

 

 

 

구글 벤다이어그램 검색

 

 

고등학교 배운 수학이 이때 이용된다. 교집합은 최소 공배수를 의미한다. 교집합은 결합 법칙이 성립하므로 3개의 수에 대한 최소 공배수도 쉽게 구할 수 있다.

 

 

 

## 관련문제

---

leetcode.com/problems/ugly-number-iii/

Ugly Number III - LeetCode