🔗 UVA-10110 Light, more light

tags: `CPE-241015` `數學(Math)`

題意

有一個走廊，走廊上有 $n$ 個燈泡，編號為 $1$ 到 $n$ 。燈泡有開關，按一次會開燈，再按一次會關燈。燈泡在一開始的時候都是關著的。

現在有一個人，他會來回走 $n$ 次，在第 $i$ 次走動時，他只會切換那些編號可以被 $i$ 整除的燈泡開關。一次完整的來回定義為走到走廊的盡頭，然後再回來。然而在返回起始位置的時候，他不會按任何開關。

現在你需要判斷在經過 $n$ 次走動後，最後一個燈泡的最終狀態是亮著還是關著。如果是亮著的話，輸出 yes，否則輸出 no。

約束條件

$1 \leq n \leq 2^{32} - 1$

LuckyCat 的中文翻譯

思路：完全平方數

在第 $i$ 次走動時，只會切換編號 $i$ 的倍數的燈泡，也就是說，對於第 $x$ 個燈泡，若 $i$ 是 $x$ 的因數，那麼在此次走動時，第 $x$ 個燈泡會被切換。

因此，對於第 $x$ 個燈泡，其被開關的次數為其因數的數量，若 $x$ 是完全平方數，則其因數的數量為奇數，否則為偶數。

因此，最後一個燈泡的狀態取決於 $n$ 是否為完全平方數。

若 $n$ 是完全平方數，則最後一個燈泡會被切換奇數次，最終狀態為亮著。
否則，最後一個燈泡會被切換偶數次，最終狀態為關著。

需要注意的是，由於 $n \leq 2^{32} - 1$ ，因此需要使用 unsigned int 來存儲 $n$ 。

複雜度分析

時間複雜度： $O(1)$ $O (1)$
- 由於在 CPU 中有專門計算平方根的指令，因此時間複雜度為 $O(1)$ 。
空間複雜度： $O(1)$

from math import isqrt # Python 3.8+

while True:
    n = int(input())
    if n == 0:
        break
    print("yes" if int(n ** 0.5) ** 2 == n else "no")

#include <bits/stdc++.h>
using uint = unsigned int;
using namespace std;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    uint n;
    while (cin >> n && n) {
        uint sqrt_n = sqrt(n);
        cout << (sqrt_n * sqrt_n == n ? "yes" : "no") << endl;
    }
    return 0;
}

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, backlight, photo background,

(1girl, solo), Frieren, frieren, long hair, very long hair, (green eyes:1.5), grey hair, pointy ears, elf,

dress, white dress, sleeveless, sleeveless dress, jewelry, earrings, bare shoulders, parted bangs, bare arms, barefoot, bare legs, collarbone, looking at viewer, blush, sitting, closed mouth, full body, flower, water, wariza, strap slip, between legs, hand between legs, lily pad,

anime girl, sitting in water, white dress, pointed ears, floating flowers, serene, fantasy, soft lighting, dreamy atmosphere,

在 ZeroJudge 上交的時後才發現 isqrt 是 Python 3.8+ 的函數，因此吃了 RE 。但 UVA 上宣稱的版本是更舊的 Python 3.5.1 ，卻可以 AC，看來 UVA 其實已經更新 Python 版本了。