Java 用于范围LCM查询

对查询进行范围设定是一种常见的数据库当前兴趣操作，存在于数据结构中，用于恢复所有输出值位于上下边界之间的记录。这个过程使用一些输入数据，以有效的方式对其进行结构化，应用于特定输入的任何子集上。范围函数（表示为range()）用于在一系列上迭代for循环。在过程开始时，我们需要将起始值声明为0。如果我们不小心漏掉了这一步，该过程将一直运行并迭代循环直到终点（-1）。

范围是可以存储在变量中的最小和最大值。它们是用运算符生成的，并用于调用变量的数组，并返回在x到y-1范围内的输出列表。

示例

假设我们有一个整数数组集合，并且我们需要以LCM(a,r)的形式评估查询。因此，我们需要以高效的方式评估查询。

LCM(a,r)表示数组中在索引a和r之间的最小公倍数。这里两个指标都是包容的。

我们都知道数学上的最小公倍数=分子的最小公倍数 / 分母的最大公约数。

因此，根据这个逻辑，我们可以遵循下面写出的划定范围的LCM查询的规则：

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作为特定编码环境中LCM操作的时间要求查找器进行声明，并且需要O(N)的时间来构建树以从编写的程序中获取输出。它还指示了该过程的空间要求。

范围LCM查询的算法

步骤1 – 开始
步骤2 – 初始化两个变量作为两个数
步骤3 – 为每个数找到存储值
步骤4 – 使用’max’函数将变量分开
步骤5 – 如果最大值能被第一个数和第二个数整除
步骤6 – 将最大值打印为LCM
步骤7 – 否则，如果不能整除，则将它增加1
步骤8 – 然后再次执行步骤五，直到一个数被打印出来
步骤9 – 重复该过程，直到找到满足条件的最大值
步骤10 – 终止

范围LCM查询的语法

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]);
}

在这个语法中，我们解释了如何在特定的编码环境中进行LCM查询。

要遵循的方法

方法1 – 通过使用段树的简单方法。
方法2 – 以一般方式找到两个数的LCM。

通过使用段树的简单方法

这个问题没有更新操作，但是单独使用简单方法是不正确的。我们需要实现一个段树来获得可能的结果。这里我们将使用一个逻辑 –

LCM(a, b) = (a*b) / GCD(a,b)

以下是实现步骤 –

为数组构建段树。
遍历段树的特定范围。
计算该范围的LCM。
打印该区段的答案。

示例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;
      }
   }
}