Problem 10637 Coprimes，互質

此題用回溯演算法就可解決。這一開始我怎麼寫都寫不出來，答案的順序錯誤，結果我上網找了一下，原來找尋這些互質的數要由小到大，而且找的下一個數要比前一個相等或來的大。

還有一點，要建構互質表，不然很容易就超過時間了，網友 藍ㄚ有兩種解題方法 ，我從這裡參考的。

所以一開始建立互質表，C 語言程式碼如下：

#define SIZE 101

int print[SIZE];
int GCD[SIZE][SIZE];
int S, t;

int gcd(int a,int b)  
{  
 if (a % b == 0){ return b;} 
 return gcd(b, a % b);
}

主程式內 ....
int a, b, n;
for(a = 1; a < SIZE; a ++)
    for(b = 1; b < SIZE; b ++)
        GCD[a][b] = gcd(a,b);

最後寫一函式，利用回溯演算法將每一種可能的方法全部試過，如果超過我們所定義數值，只有剛好等於我們定義數值，才會被列出。

void find (int index, int n, int sum)
{
    int i, j;
    if (index == t && sum == S)
    {
        printf("%d", print[0]);
        for (i = 1; i < index; i ++)
            printf(" %d", print[i]);
        printf("\n");
        return;
        
    }
    if (sum >= S) return;
    for (; n <= S - sum; n ++)
    {
           for (j = 0; j < index; j ++)
               if (GCD[print[j]][n] != 1) break;
               
           if (j == index && S - sum >= n)
           {
               print[index] = n;
               find(index + 1, n, sum + n);
           }
    }
    
}

最後在主程是如此呼叫：

scanf("%d", &n);
for (i = 1; i <= n; i ++)
{
    scanf("%d %d", &S ,&t);
    printf("Case %d:\n", i);
    find(0, 1, 0);
}

By David.K

p10637題目連結
回ACM題庫目錄
回首頁