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。
立即学习“Java免费学习笔记（深入）”；
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)ORLCM(A) = (a1 * a2 * a3 … * an) / GCD(A)
登录后复制
因此，我们将找到所有数字的 GCD 和乘积，然后从那里，我们可以在 O(1) 运算中找到该数字的 LCM。
天真的方法
最简单的方法是遍历查询数组，并为每个查询找到给定范围内的元素与 GCD 的乘积。从这两个值中找到 LCM 并返回它。让我们在代码中实现它 –
示例
// 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 时间和空间复杂度
上述代码的时间复杂度为O(Q*N*log(D))，其中Q是查询次数，N是数组中元素的数量，D是数组中存在的最大数量数组。
上述代码的空间复杂度为 O(1)，因为我们没有使用任何额外的空间。
在上面的程序中，如果查询数量等于 N，那么其时间复杂度将大于 N2，这使得该方法使用效率低下。让我们看看这是另一种方法 &miinus;
线段树方法
线段树是一种高级数据结构，用于将问题划分为多个线段，然后以 2 的幂的形式将它们连接起来。这需要一些空间用于范围查询，并在对数时间内产生结果。让我们看看它的代码 -
示例
// defining maximum sizevar MAX = 1000// makking tree var tree = new Array(4*MAX);// declaring new array var arr = new Array(MAX);// function for lcmfunction lcm(a, b){ return a*b/gcd(a,b);}// function for gcdfunction 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 r){ return 1; } // complete inside the current segment if (l = 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 treebuild(0, 5, 1);// defining query array var queries = [[1,3], [2,5]]// traversing over the array for(var i = 0; i结论
在本教程中，我们实现了一篇 JavaScript 文章来查找范围 lcm 查询。我们已经看到了两种方法，一种是时间复杂度为 O(Q*N*log(D)) 的朴素方法，另一种是时间复杂度为 O(Q*log(N)) 的线段树实现。 p>
登录后复制
以上就是用于范围 LCM 查询的 JavaScript 程序的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2692143.html
