Between Two Sets

Between Two Sets - easy

https://www.hackerrank.com/challenges/between-two-sets/problem

문제요약

정수 배열 A, B가 주어지면 다음 조건을 만족하는 정수의 갯수를 출력한다.

1. 해당 정수는 A의 모든 요소를 약수로 가진다

2. 해당 종수는 B의 모든 요소의 약수이다.

(1 <= n, m <= 10, 1 <= A[i], B[i] <= 100)

Sample Input

2 3
2 4
16 32 96

Sample Output

3

풀이

문제의 첫 번째 조건은 A의 공배수를, 두 번째는 B의 공약수를 의미한다. 즉 A의 모든 요소의 공배수이면서 B의 모든 요소의 공약수 정수의 갯수를 구한다.

처음엔 단순 계산으로 A의 큰 수부터 B의 작은 수까지 증가하면서 A의 모든 수로 나누고, B의 모든 수에서 나눠서 모두 나눠지는 수의 갯수를 구했다. 하지만 이러면 시간상 효율적이지 못하다.

빠르게 하려면 A의 최소 공배수를 구하고 B의 최대 공약수를 구해서 최대 공약수에서 최소 공배수의 배수들을 나누면서 나누어 떨어지는 수를 구하면 된다.

최대 공약수는 유클리드 호제법을 사용하고, 최소 공배수는 비슷하게 a*b/gcd를 해주면 구할 수 있다. python에서는 함수 중에 gcd를 지원하고, 이를 사용해서 lcm도 구하면 된다. gcd의 time complexity는 O(Log(n))이 된다고 한다. (n = a+b)

참고 : https://codility.com/media/train/10-Gcd.pdf