C 語言經典練習：開燈問題 (Josephus 變體) 完整解析

問題描述

有 n 盞燈 (編號 1~n)，初始全關。k 個人依序操作：

• 第 1 人：所有燈開啟
• 第 2 人：編號為 2 的倍數按開關 (開→關、關→開)
• 第 3 人：編號為 3 的倍數按開關
• ... 第 i 人：編號為 i 的倍數按開關

輸入 n, k (k ≤ n ≤ 1000)，輸出最終亮燈編號。

範例：n=7, k=3 → 輸出 1 5 6 7

數學洞察

燈 m 被按開關的次數 = m 在 [1, k] 範圍內的因數個數。

• 若因數個數為奇數 → 最終亮燈
• 若因數個數為偶數 → 最終滅燈
• 完全平方數因數個數為奇數 (因數成對，平方根單獨)

但注意：k 可能小於 n，非完全平方數也可能亮燈 (如範例中 5, 6, 7)。

模擬法實現 (O(n·k))

#include <stdio.h>
#include <string.h>

#define MAX_N 1000

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    
    int lights[MAX_N + 1] = {0};  // 0=關, 1=亮，索引 1~n
    
    for (int person = 1; person <= k; person++) {
        for (int lamp = person; lamp <= n; lamp += person) {
            lights[lamp] = !lights[lamp];  // 切換狀態
        }
    }
    
    int first = 1;
    for (int i = 1; i <= n; i++) {
        if (lights[i]) {
            if (!first) printf(" ");
            printf("%d", i);
            first = 0;
        }
    }
    printf("\n");
    return 0;
}

優化版：因數計數法 (O(n√k))

int count_divisors(int m, int k) {
    int cnt = 0;
    for (int d = 1; d * d <= m && d <= k; d++) {
        if (m % d == 0) {
            cnt++;                    // 因數 d
            int d2 = m / d;
            if (d2 != d && d2 <= k) cnt++;  // 配對因數
        }
    }
    return cnt;
}

// 主迴圈
for (int i = 1; i <= n; i++) {
    if (count_divisors(i, k) % 2 == 1) {
        // 輸出 i
    }
}

位元運算極致優化 (n ≤ 1000 時)

// 使用 unsigned long long 位元陣列 (64 燈/字)
#define WORDS ((MAX_N + 63) / 64)
unsigned long long lamps[WORDS] = {0};

for (int p = 1; p <= k; p++) {
    for (int m = p; m <= n; m += p) {
        lamps[m >> 6] ^= (1ULL << (m & 63));
    }
}

// 輸出
for (int i = 1; i <= n; i++) {
    if (lamps[i >> 6] & (1ULL << (i & 63))) { /* 輸出 */ }
}

複雜度比較

測試驗證

輸入: 7 3
過程:
初始: 0 0 0 0 0 0 0
第1人: 1 1 1 1 1 1 1  (全亮)
第2人: 1 0 1 0 1 0 1  (2,4,6 切換)
第3人: 1 0 0 0 1 1 1  (3,6 切換)
結果: 1 5 6 7  ✓

結語

開燈問題是經典的因數奇偶性應用。對於 n ≤ 1000 限制，簡單模擬法完全足夠且最不易出錯。理解數學本質有助於擴展至更大規模或變體問題 (如只輸出亮燈個數、多輪操作等)。