我正在做一个竞争性编程问题，给你一个数字数组，然后是一定数量的查询。对于每个查询，您将获得 2 个整数，即"a"和"b"。所以你应该输出数组中其余元素的 GCD（不包括 a、b 和介于两者之间的所有元素）。
例如，如果数组是：16、8、24、15、20，并且有 2 个查询 （2， 3） 和 （1， 3），则输出 1 为：1，输出 2 为：5。请注意，索引是从 1 开始的。
这是我的代码，其中我用一个函数实现了基本思想，用于查找传递给它的数组的 GCD。
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while (t-- > 0) { //This is the number of test cases
String[] s1 = br.readLine().split(" ");
int n = Integer.parseInt(s1[0]); //Number of elements in array
int q = Integer.parseInt(s1[1]); //Number of queries
String[] s2 = br.readLine().split(" ");
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(s2[i]);
}
for (int i = 0; i < q; i++) { //for each query
String[] s3 = br.readLine().split(" ");
int a = Integer.parseInt(s3[0]) - 1;
int b = Integer.parseInt(s3[1]) - 1;
int[] copy = new int[n - b + a - 1]; //this is so that the original array doesn't get messed up
int index = 0;
for (int j = 0; j < n; j++) { //filing the array without the elements of the query
if (j < a || j > b) {
copy[index] = arr[j];
index++;
}
}
int fin = gcd(copy);
System.out.println(fin);
}
}
}
private static int gcd(int a, int b) {
while (b > 0) {
int temp = b;
b = a % b; // % is remainder
a = temp;
}
return a;
}
private static int gcd(int[] input) { //simple GCD calculator using the fact that GCD(a,b,c) === GCD((a,b),c)
int result = input[0];
for (int i = 1; i < input.length; i++)
result = gcd(result, input[i]);
return result;
}
问题是我在某些部件上获得了 AC（10 个中的 6 个），其余部分则获得了 TLE。有人可以提出更好的方法来解决这个问题，因为我的方法似乎太慢了，几乎不可能进一步优化？
您只需为所有前缀和后缀预先计算 gcd。每个查询都是前缀和后缀的并集，因此回答一个查询需要O(log MAX_A)时间。这是我的代码：
import java.util.*;
import java.io.*;
public class Solution {
static int gcd(int a, int b) {
while (b != 0) {
int t = a;
a = b;
b = t % b;
}
return a;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(
new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
int tests = Integer.parseInt(br.readLine());
for (int test = 0; test < tests; test++) {
String line = br.readLine();
String[] parts = line.split(" ");
int n = Integer.parseInt(parts[0]);
int q = Integer.parseInt(parts[1]);
int[] a = new int[n];
parts = br.readLine().split(" ");
for (int i = 0; i < n; i++)
a[i] = Integer.parseInt(parts[i]);
int[] gcdPrefix = new int[n];
int[] gcdSuffix = new int[n];
for (int i = 0; i < n; i++) {
gcdPrefix[i] = a[i];
if (i > 0)
gcdPrefix[i] = gcd(gcdPrefix[i], gcdPrefix[i - 1]);
}
for (int i = n - 1; i >= 0; i--) {
gcdSuffix[i] = a[i];
if (i < n - 1)
gcdSuffix[i] = gcd(gcdSuffix[i], gcdSuffix[i + 1]);
}
for (int i = 0; i < q; i++) {
parts = br.readLine().split(" ");
int left = Integer.parseInt(parts[0]);
int right = Integer.parseInt(parts[1]);
left--;
right--;
int res = 0;
if (left > 0)
res = gcd(res, gcdPrefix[left - 1]);
if (right < n - 1)
res = gcd(res, gcdSuffix[right + 1]);
out.println(res);
}
}
out.flush();
}
}
"几乎不可能进一步优化"？ 普肖：
- 添加相邻输入元素的计算 GCD 缓存，这样就不需要重新计算它们。 例如，有一个表，其中包含
input[i]和input[j]的 GCD。 请注意，这将不超过原始输入大小的一半。 - 计算连续输入对的 GDC（以便您可以利用 #1）
这可以扩展到更大的群体，但需要更多空间。
这里的关键是一组数字A的GCD等于任何A分区的GCD。例如
GCD(16, 8, 24, 15, 20) = GCD(GCD(16, 8), GCD(24, 15, 20))
我会通过构建一些类似树的结构来利用这一事实。让我们为索引在 i 和 j 之间的元素集的 GCD 编写GCD[i, j]。对于大小为 n 的给定输入，我将存储：
GCD[1, n]
GCD[1, n/2], GCD[n/2+1, n]
...
GCD[1, 2], GCD[2, 3] ... GCD[n-1, n]
也就是说，在树的每个级别，GCD 的数量都翻了一番，计算它们的集合的大小减半。请注意，您将以这种方式存储n-1数字，因此您需要线性的额外存储空间。自下而上地计算它们，您将需要执行n-1 GCD 操作作为预处理。
对于查询，您需要组合 GCD，以便省略两个查询索引。例如，让我们有一个带有 n = 8 的数组A，我们查询(2, 4) 。
- 我们不能使用
GCD[1, 8]，因为我们需要排除 2 和 4，所以我们在树中更深入一层。 - 我们不能使用
GCD[1, 4]，但我们可以使用GCD[5, 8]，因为要排除的索引都不在其中。对于上半场，我们需要更深入。 - 我们不能使用
GCD[1, 2]，也不能使用GCD[3, 4]，所以我们更深入。 - 我们只是使用元素
A[1]和A[3].
我们现在需要计算GCD[5, 8]、A[1]和A[3]的GCD。对于查询，我们只需要进行 2 次 GCD 计算，而不是以幼稚的方式进行 5 次。
通常，您将花费O(log n)时间搜索结构，并且每个查询都需要O(log n) GCD 计算。