ZeroJudge 解題筆記：d111. 10110 - Light, more light

作者：王一哲
日期：2026年4月12日


ZeroJudge 題目連結：d111. 10110 - Light, more light

解題想法

這題考數學。第 $1$ 趟及第 $n$ 趟都會改變第 $n$ 盞燈的開關，效果抵消。只要找第 $2$ 趟到第 $(n-1)$ 趟之間改變第 $n$ 盞燈的開關次數 $cnt$，也就是找因數的數量，如果 $cnt$ 是奇數輸出 $yes$，反之輸出 $no$。可以用 for 迴圈找 $i = 2$ 到 $i = \sqrt{n}$ 之間有幾個 $n$ 的因數，如果 $i^2 \neq n$ 增加 $2$ 個因數，如果 $i^2 = n$ 增加 $1$ 個因數。所以這題可以直接用 $n$ 是否為完全平方數找答案。

Python 程式碼

找 $n$ 的因數數量，使用時間約為 14 ms，記憶體約為 8.1 MB，通過測試。

import sys

result = []
for line in sys.stdin:
    n = int(line)
    if n == 0: break
    factors = {1, n}
    for i in range(2, int(n**0.5)+1):
        if n%i == 0:
            factors.add(i)
            factors.add(n//i)
    result.append("yes\n" if len(factors)%2 == 1 else "no\n")
sys.stdout.write("".join(result))

檢查 $n$ 是否為完全平方數，使用時間約為 7 ms，記憶體約為 8.2 MB，通過測試。

import sys

result = []
for line in sys.stdin:
    n = int(line)
    if n == 0: break
    r = int(n**0.5)
    result.append("yes\n" if r*r == n else "no\n")
sys.stdout.write("".join(result))

C++ 程式碼

2025年7月27日測試，使用時間約為 2 ms，記憶體約為 80 kB，通過測試。2026年4月6日測試，使用時間約為 0 ms，記憶體約為 1.4 MB，通過測試。

#include <cstdio>
#include <set>
#include <cmath>
using namespace std;

int main() {
    int n;
    while(scanf("%d", &n) != EOF && n != 0) {
        set<int> factors = {1, n};
        for(int i=2; i<=int(sqrt(n)); i++) {
            if (n%i == 0) {
                factors.insert(i);
                factors.insert(n/i);
            }
        }
        if (factors.size()%2 == 1) puts("yes");
        else puts("no");
    }
    return 0;
}

2025年7月27日測試，使用時間約為 1 ms，記憶體約為 112 kB，通過測試。2026年4月6日測試，使用時間約為 0 ms，記憶體約為 1.5 MB，通過測試。

#include <cstdio>
#include <cmath>

int main() {
    int n;
    while(scanf("%d", &n) != EOF && n != 0) {
        int r = int(sqrt(n));
        if (r*r == n) puts("yes");
        else puts("no");
    }
    return 0;
}