범위 LCM 쿼리를 위한 JavaScript 프로그램

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입니다.

LCM과 GCD의 수학적 관계

GCD를 찾기 위해 우리는 로그 복잡도의 두 숫자의 GCD를 찾을 수 있는 유클리드 공식을 가지고 있으며 LCM과 GCD 사이에는 이러한 관계가 있습니다. -

으아악

그래서 우리는 모든 숫자의 GCD와 곱을 찾은 다음 거기에서 O(1) 연산을 통해 해당 숫자의 LCM을 찾을 수 있습니다.

순진한 방법

가장 쉬운 방법은 쿼리 배열을 반복하고 주어진 범위의 요소와 각 쿼리의 GCD의 곱을 찾는 것입니다. 이 두 값에서 LCM을 찾아 반환합니다. 코드로 구현해보자 -

예

으아악

시간과 공간의 복잡성

위 코드의 시간 복잡도는 O(Q*N*log(D))입니다. 여기서 Q는 쿼리 수, N은 배열의 요소 수, D는 쿼리에 존재하는 최대 배열 수입니다. 정렬.

위 코드의 공간 복잡도는 추가 공간을 사용하지 않기 때문에 O(1)입니다.

위 프로그램에서 쿼리 수가 N과 같으면 시간 복잡도가 N²보다 커지므로 이 방법이 비효율적입니다. 이것이 또 다른 방법인지 살펴보겠습니다 &miinus;

선분 트리 방법

세그먼트 트리는 문제를 여러 세그먼트로 나눈 다음 이를 2의 거듭제곱으로 연결하는 데 사용되는 상위 수준 데이터 구조입니다. 이를 위해서는 범위 쿼리를 위한 약간의 공간이 필요하며 로그 시간에 결과를 생성합니다. 코드를 살펴보겠습니다 -

예

으아악

결론

이 튜토리얼에서는 범위 lcm 쿼리를 찾기 위한 JavaScript 기사를 구현했습니다. 우리는 두 가지 방법을 보았습니다. 하나는 시간 복잡도가 O(Q*N*log(D))인 순진한 방법이고, 다른 하나는 시간 복잡도가 O(Q*log(N))인 선분 트리입니다. p>

위 내용은 범위 LCM 쿼리를 위한 JavaScript 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!