有 n 盞燈，初始全滅。k 個人依次操作：第 i 個人 (1 ≤ i ≤ k) 將編號為 i 的倍數的燈切換狀態 (開→關，關→開)。最終輸出亮著的燈編號。
即：燈 j 被切換的次數等於 j 在 [1, k] 範圍內的約數個數。奇數次亮，偶數次滅。
約數通常成對出現 (d, j/d)，只有當 j = d² 時約數不成對 (d 自身配對)。因此：
最終亮燈的編號，恰好是不超過 min(n, k) 的完全平方數。
若 k ≥ n，答案就是 1, 4, 9, 16, ... ≤ n。若 k < n，則為 1, 4, 9, ... ≤ k 且平方數 ≤ n。
#include#include #include int main() { int n, k; while (scanf("%d %d", &n, &k) == 2) { bool *lamp = calloc(n + 1, sizeof(bool)); // 索引 1..n for (int i = 1; i <= k; ++i) for (int j = i; j <= n; j += i) lamp[j] = !lamp[j]; bool first = true; for (int j = 1; j <= n; ++j) if (lamp[j]) { if (!first) putchar(' '); printf("%d", j); first = false; } puts(""); free(lamp); } return 0; }
時間 O(n log n) (調和級數)，空間 O(n)。適合 n ≤ 10⁵。
#include#include int main() { int n, k; while (scanf("%d %d", &n, &k) == 2) { int limit = (k < n) ? k : n; int max_root = (int)sqrt(limit); for (int i = 1; i <= max_root; ++i) { int sq = i * i; if (sq > n) break; // 當 k > n 時需額外判斷 if (i > 1) putchar(' '); printf("%d", sq); } puts(""); } return 0; }
時間 O(√min(n,k))，空間 O(1)。極快，支持 n, k 至 10¹²+ (用 64 位整數)。
int max_root = 0; while ((max_root + 1) * (max_root + 1) <= limit) ++max_root;
| n | k | 輸出 | 說明 |
|---|---|---|---|
| 10 | 10 | 1 4 9 | 完全平方數 ≤ 10 |
| 10 | 3 | 1 | k=3, 僅 1²=1 ≤ 3 且 ≤ 10 |
| 100 | 1000 | 1 4 9 16 25 36 49 64 81 100 | k>n, 受限於 n |
| 1 | 1 | 1 | 最小規模 |
| 0 | 5 | (空行) | n=0 邊界 |
i*i 循環，C 需手寫大整數或用 GMP。| 方法 | 時間 | 空間 | 適用場景 |
|---|---|---|---|
| 雙循環模擬 | O(n log n) | O(n) | 教學演示、小規模、需完整過程記錄 |
| 平方數直接輸出 | O(√n) | O(1) | 競賽/面試/生產、超大規模、極致性能 |
#include#include int main() { long long n, k; while (scanf("%lld %lld", &n, &k) == 2) { long long limit = k < n ? k : n; long long r = sqrt((double)limit); while ((r+1)*(r+1) <= limit) ++r; // 修正浮點誤差 while (r*r > limit) --r; for (long long i = 1; i <= r; ++i) { if (i > 1) putchar(' '); printf("%lld", i*i); } putchar('\n'); } return 0; }
開燈問題是數論洞察力的經典考察：從 O(n log n) 模擬到 O(√n) 數學解法，體現了「先思考數學本質，再寫代碼」的工程智慧。面試或競賽中，直接給出平方數解法並說明約數成對論證，是滿分答案。
