数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学Java区间最小公倍数查询程序
区间查询是数据库中常见的当前热点操作，存在于数据结构中，用于检索输出值位于上限和下限之间的所有记录。此过程使用某些输入数据，以有效的方式对特定输入的任何子集进行结构化。 range 函数（表示为 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; 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 − 如果 max 可被第一个数字和第二个数字整除。
步骤 6 − 将 max 作为最小公倍数打印出来。
步骤 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
public class roudtp {
static final int MAX = 1000;
static int tree[] = new int[4 * MAX];
static int arr[] = new int[MAX];
static int gcd(int a, int b) {
if (a == 0) {
return b;
}
return gcd(b % a, a);
}
static int lcm(int a, int b) {
return a * b / gcd(a, b);
}
static 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);
int left_lcm = tree[2 * node];
int right_lcm = tree[2 * node + 1];
tree[node] = lcm(left_lcm, right_lcm);
}
static 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);
}
public static void main(String[] args) {
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] = 16;
arr[9] = 1;
arr[10] = 44;
build(1, 0, 10);
System.out.println(query(1, 0, 10, 7, 5));
System.out.println(query(1, 0, 10, 16, 10));
System.out.println(query(1, 0, 10, 44, 10));
}
}
输出
1 1 1
以一般方式查找两个数的最小公倍数
在此程序中，我们有两个整数 n1 和 n2。这两个数中较大的一个存储在 max 中。
示例 2
public class Main {
public static void main(String[] args) {
int n1 = 7, n2 = 16, lcm;
lcm = (n1 > n2) ? n1 : n2;
// Always true as a function
while(true) {
if( lcm % n1 == 0 && lcm % n2 == 0 ) {
System.out.printf("The LCM of %d and %d is %d.", n1, n2, lcm);
break;
}
++lcm;
}
}
}
输出
The LCM of 7 and 16 is 112.
结论
在今天的文章中，我们学习了如何使用特定编码环境编写程序来找出给定区间最小公倍数查询的范围。
167 次浏览
