LCM은 최소 공배수를 나타내며, 숫자 집합의 LCM은 주어진 집합에 존재하는 모든 숫자로 나누어지는 모든 숫자 중에서 가장 작은 숫자입니다. 주어진 문제에 대한 설명과 함께 전체 코드를 살펴보겠습니다. 이 기사에서는 일련의 LCM 쿼리에 대한 JavaScript 프로그램을 구현합니다.
이 문제에서는 정수를 포함하는 배열과 주어진 배열 범위를 나타내는 숫자 쌍을 포함하는 또 다른 배열 쿼리가 제공되며 해당 범위에 있는 모든 요소의 LCM을 계산해야 합니다. 예를 들어 -
주어진 배열이 [1, 2, 3, 4, 5, 6]이고 쿼리 배열이 [[1,3], [2,5]]인 경우 첫 번째 쿼리 요소는 [2, 3 , 4] 및 12는 LCM입니다.
두 번째 쿼리 요소가 [3, 4, 5, 6]인 경우 LCM은 60입니다.
GCD를 찾기 위해 우리는 로그 복잡도의 두 숫자의 GCD를 찾을 수 있는 유클리드 공식을 가지고 있으며 LCM과 GCD 사이에는 이러한 관계가 있습니다. -
으아악그래서 우리는 모든 숫자의 GCD와 곱을 찾은 다음 거기에서 O(1) 연산을 통해 해당 숫자의 LCM을 찾을 수 있습니다.
가장 쉬운 방법은 쿼리 배열을 반복하고 주어진 범위의 요소와 각 쿼리의 GCD의 곱을 찾는 것입니다. 이 두 값에서 LCM을 찾아 반환합니다. 코드로 구현해보자 -
위 코드의 시간 복잡도는 O(Q*N*log(D))입니다. 여기서 Q는 쿼리 수, N은 배열의 요소 수, D는 쿼리에 존재하는 최대 배열 수입니다. 정렬.
위 코드의 공간 복잡도는 추가 공간을 사용하지 않기 때문에 O(1)입니다.
위 프로그램에서 쿼리 수가 N과 같으면 시간 복잡도가 N2보다 커지므로 이 방법이 비효율적입니다. 이것이 또 다른 방법인지 살펴보겠습니다 &miinus;
세그먼트 트리는 문제를 여러 세그먼트로 나눈 다음 이를 2의 거듭제곱으로 연결하는 데 사용되는 상위 수준 데이터 구조입니다. 이를 위해서는 범위 쿼리를 위한 약간의 공간이 필요하며 로그 시간에 결과를 생성합니다. 코드를 살펴보겠습니다 -
이 튜토리얼에서는 범위 lcm 쿼리를 찾기 위한 JavaScript 기사를 구현했습니다. 우리는 두 가지 방법을 보았습니다. 하나는 시간 복잡도가 O(Q*N*log(D))인 순진한 방법이고, 다른 하나는 시간 복잡도가 O(Q*log(N))인 선분 트리입니다. p>
위 내용은 범위 LCM 쿼리를 위한 JavaScript 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!