UVa 11461 題解 — C++

此筆記為UVa 11461的題目詳解，包含解題思路、C++範例程式碼。

Square Numbers (ZeroJudge d186.)

題目

完全平方數就是平方根為整數的整數。例如 1, 4, 81 就是完全平方數。給你兩個整數 a 和 b，請你求出 a 與 b 之間 (含) 有幾個完全平方數。

輸入 / 輸出說明

輸入說明	輸出說明
輸入檔最多有 201 行的輸入。每行有兩個整數 a 和 b (0<a≤b≤100000)。輸入以含有兩個 0 的一行作為結束，請勿對這行做任何輸出。	對於每行輸入，請產生一行輸出，這行含有一個整數，代表 a 與 b 之間 (含) 有多少個完全平方數。

解題思路

這一題是求完全平方數，看似直接求

$\surd a$ 到

$\surd b$ 之間有多少個整數即可，所以應該可以輸出

$\surd b$ -

$\surd a$ + 1（因為要包含下限所以要加一）。

但如果你這麼做就送出去，那麼你應該會得到一個 WA，因為你沒有考慮到 小數點後 b - a 可能大於 0，轉換為整數時就會多 1，因此要將

$\surd a$ 無條件進位，程式應該要寫成 sqrt(b) - ceil(sqrt(a)) + 1。

ex. 輸入 82 200
應該是介於

$\surd 82$

$\approx$ 9.06 到

$\surd 200$

$\approx$ 14.14 之間的完全平方數。
若直接使用 t = sqrt(200) - sqrt(82) + 1; 就會是 6（14.14 - 9.06 + 1 = 6.08 取整數 = 6），但正確答案應該是 5（14 - 10 + 1 = 5），因為 9 * 9 = 81 < 82，9 不在範圍內，而我們多算了 9。

範例程式碼

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, a, b, t;
	
	while (cin >> a >> b) {
		if (a == 0 && b == 0)
			break;
			
		t = sqrt(b) - ceil(sqrt(a)) + 1;
		
		cout << t << endl;
	} 

	return 0;
}

運行結果

AC (2ms, 336KB)

tags: CPE 1星

查看更多資訊請至：https://www.tseng-school.com/