Например, если массив: 16, 8, 24, 15, 20 и есть 2 запроса (2, 3) и (1, 3), то выходной сигнал 1 равен: 1, а выходной сигнал 2 равен: 5.
Обратите внимание, что индексация На основе 1.
Вот мой код, в котором я реализовал основную идею с функцией поиска НОД массива, переданного в него.
Код: Выделить всё
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;
}
