ZOJ 1003 Crashing Balloon：DFS 分解因子判斷遊戲勝負

遊戲規則

100 個氣球編號 1~100。兩玩家初始分數 1，踩破氣球後分數乘以氣球編號。最終宣佈分數，較大者勝。給定兩分數 a, b，判斷誰可能作弊（分數不可由 1~100 子集乘積得到）。

DFS 因子分解算法

int f1, f2; // 標記 a, b 是否可分解

void DFS(int m, int n, int k) { // m,n 為待分解數，k 從 100 遞減
    if (n == 1) { f2 = 1; if (m == 1) f1 = 1; }
    if (f1 && f2 || k == 1) return;
    if (m % k == 0) DFS(m/k, n, k-1);
    if (n % k == 0) DFS(m, n/k, k-1);
    DFS(m, n, k-1); // 不使用 k
}

int main() {
    int a, b, temp;
    while (scanf("%d %d", &a, &b) >= 0) {
        if (a < b) { temp=a; a=b; b=temp; } // 保證 a >= b
        f1 = f2 = 0;
        DFS(a, b, 100);
        temp = (!f1 && f2) ? b : a; // 若 a 不能分解但 b 能，則 b 為真實分數
        printf("%d\n", temp);
    }
    return 0;
}

核心邏輯

• 從 100 遞減嘗試因子，三種選擇：分解 m、分解 n、跳過。
• 若 a 不能完全分解（f1=0）而 b 能（f2=1），說明 a 作弊，輸出 b；反之亦然。
• 若均能分解或均不能，輸出較大值（題目保證有解）。