C語言經典練習：開燈問題（因數翻轉模擬）

問題描述

有 n 盞燈（編號 1~n），初始全滅。
第 1 人翻轉所有燈（全亮）。
第 2 人翻轉 2 的倍數編號燈。
第 3 人翻轉 3 的倍數編號燈。
... 第 k 人翻轉 k 的倍數。
最終輸出亮著的燈編號。
條件：k ≤ n ≤ 1000。

核心洞察

燈 i 被翻轉次數等於其在 [1, k] 範圍內的因數個數。
若因數個數為奇數 → 亮；偶數 → 滅。
完全平方數因數個數為奇數（因平方根只算一次），故完全平方數且 ≤ k 的燈最終亮。
但題目要求模擬過程，直接模擬即可（n ≤ 1000，複雜度 O(nk) 完全可接受）。

模擬代碼

#include 
#include 

#define MAX 1010
int a[MAX];

int main() {
    int n, k;
    memset(a, 0, sizeof(a));  // 0 滅，1 亮
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
            if (j % i == 0) a[j] = !a[j];
        }
    }
    for (int i = 1; i <= n; i++) {
        if (a[i]) printf("%d%c", i, (i == n) ? '\n' : ' ');
    }
    return 0;
}

樣例測試

輸入：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
第3人：1 0 0 0 1 1 1
輸出：1 5 6 7

優化思路（數學解）

直接輸出 i*i ≤ n 且 i ≤ k 的 i*i，但模擬法更直觀、通用（如 k < n 時非完全平方數也可能亮）。

總結

本題考察陣列模擬、雙重循環與取模運算。n ≤ 1000 時暴力模擬最穩健；理解因數奇偶性可推導數學解，但非必須。