数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++区间最小公倍数查询程序
范围查询是数据库中常见的当前热点操作，存在于数据结构中，用于恢复所有输出值位于上限和下限之间的记录。此过程使用一些输入数据，以高效的方式对特定输入的任何子集进行结构化。range() 函数用于迭代 for 循环。我们需要在过程开始时将起始值声明为 0。如果我们以某种方式错过了此步骤，则该过程将运行并迭代循环直到结束 (-1)。
范围是可以在变量中存储的最小值和最大值。它们由运算符生成，并用于调用变量数组。此范围返回 x 到 y-1 之间的输出列表。
示例
假设我们有一个整数数组，我们需要以 LCM(a,r) 的形式计算查询。因此，我们必须以高效的方式计算查询。
LCM(a,r) 表示数组中索引 a 和 r 之间存在的最小公倍数。此处，两个索引都是包含的。
数学上我们都知道：最小公倍数 = 分子最小公倍数 / 分母最大公约数。
因此，使用此逻辑，我们可以遵循下面编写的区间最小公倍数查询规则
LCM(a, r) = LCM(arr[a], arr[a+1] , ......... ,arr[r-1], arr[r])
应用此逻辑
输入：
arr[0] = 5; arr[1] = 7; arr[2] = 5; arr[3] = 2; arr[4] = 10; arr[5] = 12; arr[6] = 11; arr[7] = 17; arr[8] = 14; arr[9] = 1; arr[10] = 44; C++ Program for range LCM queries build(1, 0, 10); cout << query(1, 0, 10, 2, 5) << endl; cout << query(1, 0, 10, 5, 10) << endl; cout << query(1, 0, 10, 0, 10) << endl;
输出：
60 15708 78540
此特定过程的时间复杂度表示为 O(Log N * Log n)。其中 N 是数组中存在的元素总数。我们需要将 Log n 声明为在特定编码环境中查找最小公倍数操作所需的时间，并且需要 O(N) 时间来构建树以从编写的程序中获得输出。它还表示该过程的空间需求。
区间最小公倍数查询算法：
步骤 1 − 开始
步骤 2 − 初始化两个数字变量。
步骤 3 − 查找每个数字的存储值。
步骤 4 − 使用 'max' 函数分离变量。
步骤 5 − 如果最大值可以被第一个数字和第二个数字整除。
步骤 6 − 打印最大值作为最小公倍数。
步骤 7 − 否则，如果不能整除，则将其加 1。
步骤 8 − 然后再次转到步骤五，直到打印出一个数字。
步骤 9 − 重复此过程，直到找到满足条件的最大值。
步骤 10 − 终止。
区间最小公倍数查询语法
int find_therangelcm(int a, int tl, int ts, int r) {
if (r > t[a])
return -1;
if (tl == ts)
return tl;
int tm = (tl + ts) / 2;
if (t[a*2] >= r)
return find_therangelcm(a*2, tl, tm, r);
else
return find_therangelcm(a*2+1, tm+1, ts, r - t[a*2]);
}
在此语法中，我们解释了如何在特定编码环境中进行区间最小公倍数查询。
方法
方法 1 − 使用线段树的朴素方法。
方法 2 − 以一般方式查找两个数的最小公倍数。
使用线段树的朴素方法
此问题没有更新操作，但仅使用朴素方法是不正确的。我们需要实现线段树才能获得可能的结果。在这里，我们将使用以下逻辑：
LCM(a, b) = (a*b) / GCD(a,b)
以下是实现步骤：
为数组构建线段树。
遍历线段树的特定范围。
计算该范围内的最小公倍数。
打印该线段的答案。
示例 1
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
int tree[4 * MAX];
int arr[MAX];
int gcd(int a, int b) {
if (a == 0)
return b;
return gcd(b % a, a);
}
int lcm(int a, int b) { return a * b / gcd(a, b); }
void build(int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
return;
}
int mid = (start + end) / 2;
build(2 * node, start, mid);
build(2 * node + 1, mid + 1, end);
// build the parent
int left_lcm = tree[2 * node];
int right_lcm = tree[2 * node + 1];
tree[node] = lcm(left_lcm, right_lcm);
}
int query(int node, int start, int end, int l, int r) {
if (end < l || start > r)
return 1;
if (l <= start && r >= end)
return tree[node];
int mid = (start + end) / 2;
int left_lcm = query(2 * node, start, mid, l, r);
int right_lcm = query(2 * node + 1, mid + 1, end, l, r);
return lcm(left_lcm, right_lcm);
}
int main() {
arr[0] = 16;
arr[1] = 7;
arr[2] = 10;
arr[3] = 22;
arr[4] = 1;
arr[5] = 97;
arr[6] = 11;
arr[7] = 31;
arr[8] = 24;
arr[9] = 15;
arr[10] = 44;
build(16, 0, 10);
cout << query(16, 0, 10, 22, 15) << endl;
cout << query(22, 0, 16, 15, 10) << endl;
cout << query(1, 0, 10, 0, 10) << endl;
return 0;
}
输出
1 1 0
以一般方式查找两个数的最小公倍数
在此程序中，我们有两个整数 n1 和 n2。这两个数字的最大值存储在 max 中。
示例 2
#include <iostream>
using namespace std;
int main() {
int n1, n2, max;
cout << "Enter two numbers to find LCM: ";
cin >> n1 >> n2;
max = (n1 > n2) ? n1 : n2;
do {
if (max % n1 == 0 && max % n2 == 0) {
cout << "LCM = " << max;
break;
}
else
++max;
} while (true);
return 0;
}
输出
Enter two numbers to find LCM:0
结论
在今天的这篇文章中，我们学习了如何使用特定的编码环境编写程序来找出给定区间最小公倍数查询的范围。
浏览量 159
