JavaScript 范围LCM查询的程序

LCM代表最小公倍数，而一组数的LCM是可被该组数中的所有数整除的最小数。我们将看到带有给定问题解释的完整代码。在本文中，我们将实现用于范围LCM查询的JavaScript程序。

问题介绍

在这个问题中，我们给定一个包含整数的数组，还有一个包含成对数字的查询数组，表示我们要计算该给定范围内所有元素的LCM。示例 –

如果给定的数组是：[1, 2, 3, 4, 5, 6]，查询数组是：[[1, 3], [2, 5]]，那么对于第一个查询来说，元素是[2, 3, 4]，LCM为12。

对于第二个查询来说，元素是[3, 4, 5, 6]，LCM为60。

LCM和GCD之间的数学关系

我们有一个欧几里得公式来找到最大公约数（GCD），通过它我们可以以对数复杂度找到两个数字的GCD，而且LCM和GCD之间有一个关系 –

LCM and GCD of a given set A {a1, a2, a3 …. , an} is:
LCM(A) * GCD(A) = (a1 * a2 * a3* … * an)
OR
LCM(A) = (a1 * a2 * a3 … * an) / GCD(A)

因此，我们将找出所有数字的最大公约数和乘积，然后从中可以使用O(1)操作找出数字的最小公倍数。

原生方法

原生方法是遍历查询数组，并且对于每个查询，在给定范围内找到元素的乘积和最大公约数。从两个值中找出最小公倍数并返回。让我们在代码中实现它−

示例

// function to find the gcd of the given number 
function gcd(a,b){
   if (a == 0) {
      return b;
   }
   else {
      return gcd(b%a,a);
   }
}

// function to find the lcm 
function lcmRange(arr, l, r){

   // taking gcd as zero because gcd of 0 with any number is that same number 
   var cur_gcd = 0
   var product = 1
   var cur_lcm = arr[l]
   for(var i = l+1 ;i <= r; i++) {
      product = cur_lcm * arr[i];
      cur_gcd = gcd(cur_lcm, arr[i])
      cur_lcm = product/cur_gcd
   }
   console.log("The LCM of the element in the given range from " + l + " to " + r + " is: " + cur_lcm);
}

// defining the array 
var arr = [ 1, 2, 3, 4, 5, 6]

// defining the queries array 
var queries = [[1,3], [2,5]]

// traversing over the array 
for(var i = 0; i< queries.length; i++){
   lcmRange(arr,queries[i][0], queries[i][1])
}

时间和空间复杂度

上述代码的时间复杂度为O(Q*N*log(D))，其中Q是查询的数量，N是数组中元素的数量，D是数组中最大的数。

上述代码的空间复杂度为O(1)，因为我们没有使用额外的空间。

在上面的程序中，如果查询的数量等于N，那么它的时间复杂度将大于N^2，这使得这种方法使用起来低效。让我们看看另一种方法。

线段树方法

线段树是一种高级数据结构，用于将问题分段，然后将它们按照2的幂的形式合并。它在一些空间上产生范围查询的结果，并以对数时间产生结果。让我们看看它的代码.

示例

// defining maximum size
var MAX = 1000

// makking tree 
var tree = new Array(4*MAX);

// declaring new array 
var arr = new Array(MAX);

// function for lcm
function lcm(a, b){
   return a*b/gcd(a,b);
}

// function for gcd
function gcd(a, b){
   if (a == 0)  {
      return b
   }
   else{
      return gcd(b%a,a);
   }
}

// Function to creata a segment tree 
function build(first, last, cur_node){

   // base condition 
   if (first == last){
      tree[cur_node] = arr[first];
      return;
   }
   var mid = (first + last)/2
   mid = Math.floor(mid);

   // creating left and right segments
   build(first, mid, 2*cur_node);
   build(mid+1, last, 2*cur_node + 1);

   // build the parent for current 
   var lcm_l = tree[2*cur_node];
   var lcm_r = tree[2*cur_node+1];
   tree[cur_node] = lcm(lcm_l, lcm_r);
}

// Function to make queries for array range 
function query(first, last, l, r, cur_node){

   // section out of current range

   // 1 is safe to return 
   if (last < l || first > r){
      return 1;
   }

   // complete inside the current segment
   if (l <= first  && r >= last)
   return tree[cur_node];

   // partially inside the current segment 
   var mid = (first+last)/2;
   mid = Math.floor(mid)
   var lcm_l = query(first, mid, l, r, 2*cur_node);
   var lcm_r = query(mid+1, last, l, r, 2*cur_node+1);
   return lcm(lcm_l, lcm_r);
}

// defining the array 
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
arr[3] = 4;
arr[4] = 5;
arr[5] = 6;

// build the segment tree
build(0, 5, 1);

// defining query array 
var queries = [[1,3], [2,5]]

// traversing over the array 
for(var i = 0; i< queries.length; i++){
   console.log("The LCM of the element in the given range from " + queries[i][0] + " to " + queries[i][1] + " is: " + query(0,5,queries[i][0],queries[i][1],1) );
}