[CPE一星49題] UVA11461 - Square Numbers 題目解析與實作

作者： 中國醫藥大學蔡豐聲


編輯製作： 蔡豐聲、李心潔

單位： 中國醫藥大學 醫療資訊學系 程式俱樂部 

 YT： https://youtu.be/EzazVuX383g

## 題目資訊

  • 題目名稱： Square Numbers
  • 編號： CPE10480, UVA11461

## 題目解析

完全平方數（Square Numbers）是指可以寫成某個整數平方的數，例如 $1, 4, 9, 16, 25 \dots$ 等。本題要求給定一個範圍 $[a, b]$，計算在此區間內共有多少個完全平方數。

## 輸入說明

  • 每組測試資料包含兩個整數 $a$ 和 $b$ ($0 < a \le b \le 100000$)。

  • 當輸入為 0 0 時，代表測試結束 。

## 輸出說明

  • 對於每組測試資料，輸出一個整數，代表在 $a$ 到 $b$ 之間（包含 $a, b$）完全平方數的個數。

## 範例測試

  • 輸入： 
                  1 4   
                  1 10   
                  0 0  
  • 輸出：                 
                  2  
                  3  

## 解題思路

  • 數學原理：我們可以利用平方根函數 sqrt() 來判斷一個數是否為完全平方數 。如果一個數 $x$ 的平方根取整數後，再平方等於 $x$，則 $x$ 為完全平方數（即 int(sqrt(x))**2 == x）。
  • 實作步驟：
  1. 使用 while 迴圈持續讀取 $a$ 與 $b$，直到兩者皆為 0 。
  2. 在區間 $[a, b]$ 中遍歷每一個數字，檢查其是否為完全平方數，並計數 。
  • 效能優化建議：雖然直接遍歷可解此題，但更好的做法是計算 $\lfloor \sqrt{b} \rfloor - \lceil \sqrt{a} \rceil + 1$。

## 實作程式碼 (Python)

import math

while True:
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        break

    small = math.ceil(a ** 0.5)
    big = math.floor(b ** 0.5)
    print(big - small + 1)
---
本著作採用創用 CC 姓名標示-非商業性-禁止改作 3.0 台灣 授權條款授權。
本部落格的免責聲明。
程式俱樂部YT頻道 https://www.youtube.com/@tsai-cai