Поиск наибольшего общего делителя (GCD) массива, за исключением некоторых элементов за минимальное время

Question

Я занимался конкурсным программированием, в котором вам задан массив чисел, а затем определенное количество запросов. Для каждого запроса вам присваивается 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 на некоторых из частей (6 из 10), и TLE на остальных. Может ли кто-нибудь предложить лучший метод для решения этой проблемы, поскольку мой подход кажется слишком медленным и почти невозможно оптимизировать?

Answer 1

«Практически невозможно оптимизировать»? Тьфу:

1. Добавить кэш вычисленного ГКДА смежных элементов ввода таким образом, они не должны быть повторно вычислены. Например, у вас есть таблица, содержащая GCD input[i] и input[j]. Обратите внимание, что это будет не более половины размера исходного ввода.
2. Вычисляется GDC последовательных пар входов (так что вы можете воспользоваться # 1)

Это может быть распространена на более крупные группы, за счет большего пространства.

Answer 2

Здесь важно, чтобы GCD набора чисел A был равен GCD GCD любого раздела A. Например,

GCD(16, 8, 24, 15, 20) = GCD(GCD(16, 8), GCD(24, 15, 20)) 

Я бы использовал этот факт, построив какую-нибудь древовидную структуру. Давайте напишем GCD[i, j] для 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] 

То есть, на каждом уровне дерева количества ГКДА удваивается и размером множеств, над которыми они вычисляются половинки. Обратите внимание, что вы будете хранить n-1 номеров таким образом, поэтому вам потребуется линейное дополнительное хранилище. Вычисляя их снизу вверх, вам нужно будет выполнить n-1 операции GCD в качестве предварительной обработки.

Для запросов вам необходимо объединить GCD таким образом, чтобы точно два индекса запроса были исключены. В качестве примера давайте рассмотрим массив A с n = 8 и мы запросим (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]. Для запроса нам нужно сделать всего 2 вычисления GCD, а не 5 наивным образом.

В общем, вы потратите O(log n) на поиск структуры и потребуется O(log n) Вычисление GCD для каждого запроса.

Answer 3

Вы можете просто прекомпретировать 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(); 
    } 
}