Сгенерировать список чисел, GCD которых указан

Question

Мне дали 2 цифры: G & n. Найти весь возможный список n чисел [A0, A1, A2, ....... Ai, ....., Aj ... An], gcd - G, следующих нижеприведенным ограничениям:

• GCD (A0, A1, A2, ...., Ai, ....., An-1) = G.
• Ai> G, ∀ 0 ≤ i < n.

• Ай ≥ Aj, ∀ ≤ J я

  определить функцию, сумма (А) = А0 + A1 + .... + An-1. Если несколько последовательностей удовлетворяют первым трем свойствам, напечатайте тот, который минимизирует функцию суммы (A).

Пример: G = 4, N = 3. Таким образом, возможен список номеров: [8, 12, 20].

Мой подход: я создаю список из n простых чисел и напечатал G * prime [j] для всех 0 < = j < n. Но это, похоже, не работает.

public class GeneratingSequence { 

    private static int MAX = 1000; 
    private static int MAX1 = 8000; 

    private void sieve(int[] a) 
    { 
     boolean[] b = new boolean[MAX1]; 
     int aIndex = 0; 

     for(int i = 1; i < MAX1; i++) 
     { 
      if(!b[i]) 
      { 
       //System.out.print((i + 1) + " "); 

       if(aIndex < a.length) 
        a[aIndex++] = i + 1; 

       markMultiples(i + 1, b); 
      } 
     } 
    } 

    private void markMultiples(int n, boolean[] b) 
    { 
     int i = 2, num; 

     while((num = i * n) <= MAX1) 
     { 
      b[num - 1] = true; 
      i++; 
     } 
    } 

    public static void main(String[] args) throws NumberFormatException, IOException 
    { 
     GeneratingSequence gs = new GeneratingSequence(); 

     BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 

     int[] primes = new int[MAX]; 

     gs.sieve(primes); 

     int T = Integer.parseInt(br.readLine()); 

     for(int i = 0; i < T; i++) 
     { 
      String[] a = br.readLine().split("\\s"); 
      long g = Long.parseLong(a[0]); 
      int n = Integer.parseInt(a[1]); 

      for(int j = 0; j < n; j++) 
      { 
       long t = g*primes[j]; 
       System.out.print(t + " "); 
      } 

      System.out.println(); 
     } 
    } 
} 

Answer 1

Первое ограничение говорит нам, что все должны быть целыми числами, кратными G, позволяет сказать, что A _я = F _я * G и что НОД в F _я должен быть 1.

от второго ограничения мы знаем, что F _я> = 2.

Третье ограничение говорит, последовательность должна быть неубывающей.

последовательность, которая выполняет все три ограничения является:

[2 * G, 2 * G, 2 * G, ..., 2 * G, 3 * G]

и эта последовательность также имеет наименьшую сумму.