生成給定GCD的數字列表

我給出了2個數字說G & n。查找所有可能的n個數字列表[A0，A1，A2，....... Ai，.....，Aj ... An]，其gcd爲G，遵循以下約束條件：生成給定GCD的數字列表

GCD（A0，A1，A2，...，Ai，...，An-1）= G
Ai> G，∀0≤i < n。
艾≥AJ，∀Ĵ≤我

定義一個函數，和（A）= A0 + A1 + ... + An-1的。如果多個序列滿足前三個屬性，則打印最小化sum（A）函數的序列。

例如：G = 4，N = 3所以一個可能的數字列表：[8,12,20]。

我的方法：我生成一個n素數列表並打印所有的G *素數[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(); 
     } 
    } 
}

來源

2015-10-25 coderx

請告訴我們，你已經嘗試做你自己的功課，以及你卡在哪裏。 –

嘿@robmayoff - 請看看編輯和建議的解決方案。 – coderx

你確定*這是任務嗎？因爲除非我遺漏了一些東西，GCD（2 * G，3 * G，4 * G，5 * G，...（n + 1）* G）= G，這太簡單了，可以通過分析來解決。 – Amit

第一個條件告訴我們，所有A都爲G的整數倍，可以說一個_我 = F _我 * G和殲_的GCD我必須爲1。

從第二約束我們知道那個F _我> = 2

第三約束表示，序列必須非遞減。

其滿足所有三個約束序列是：

[2 * G，2 * G，2 * G，...，2 * G，3 * G]

和該序列也總和最小。

來源

2015-10-27 05:00:54 Henry

生成給定GCD的數字列表

回答

相關問題