#44197: python 解 (關鍵字: 完全平方數)
sam851015@gmail.com
(多挖鼻孔有益身心健康)
學校
:
不指定學校
編號 : 277705
來源 : [123.192.228.253]
最後登入時間 ：
2024-11-09 20:16:56
簡單的作法就是遍歷所有可能的數字，一個一個檢查，能得到答案，但也同時會到 TLE
把題目簡化來看，所謂的 quirksome number 其實都是完全平方數，所以我們並不需要遍歷 0 - 99999999 每個數字，逐一檢查每個數字是否是 quirksome number，而是檢查小於 0 - 99999999 之間的完全平方數即可，不是完全平方數的可以直接跳過無視，不用考慮。
那該如何找 0 - 99999999 之間的完全平方數呢?
最簡單的的做法就是窮舉，直接遍歷 0 - 9999 之間的所有數字，取其平方即可
為什麼只取到 9999 ? 因為 10000 的平方就超過八位數了，肯定不是 quirksome number
|
# 考慮數字最大為 1e9-1 ，將該數字分割成兩半後相加，應介於 0 - 9999 之間
# 故開一個陣列，用來紀錄任意數字分割成兩半、相加、取平方的結果
quirk_number = [i * i for i in range(10000)]
while True:
try:
n = int(input())
except EOFError:
exit()
else:
for i in range(len(quirk_number)):
# 當數值超出範圍就退出循環
if quirk_number[i] >= pow(10, n):
break
# 將數字分成左右兩半，分別以 lft 和 rgt 表示
lft, rgt = quirk_number[i] // pow(10, n // 2), quirk_number[i] % pow(10, n // 2)
if pow(lft + rgt, 2) == quirk_number[i]:
print(str(quirk_number[i]).zfill(n))
|
最後輸出時，位數不夠的記得要用 zfill 在前面補 0
ZeroJudge Forum