a059 - 完全平方和

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算給定範圍 [a, b] 內所有完全平方數的和。輸入包含多組測試案例，每組案例提供一個範圍 a 和 b，程式需要計算並輸出該範圍內完全平方數的和。

解題思路

對於每組測試案例，程式遍歷從 a 到 b 的所有整數。對於每個整數 j，計算其平方根。如果平方根是整數（即 sqrt(j) 等於 sqrt(j)），則 j 是完全平方數，將其加到總和 sum 中。最後，輸出每組案例的 sum 值。

複雜度分析

• 時間複雜度: O(N * sqrt(B))，其中 N 是測試案例的數量，B 是 b 的最大值。對於每個測試案例，需要遍歷 [a, b] 範圍內的每個數字，並計算平方根，時間複雜度為 O(b-a)。由於需要計算平方根，時間複雜度可以近似為 O(sqrt(b))。
• 空間複雜度: O(1)，程式只使用了常數級別的額外空間。

程式碼

#include <iostream>
#include <math.h>

using namespace std;

int main (){
	
	int n=0;
	int a=0,b=0;
	long long int sum=0;
	
	while(cin >> n){
		for(int i=1;i<=n;i++){
			cin >> a >> b;
			for(int j=a;j<=b;j++){
				float x=sqrt(j);
				if(x==sqrt(j)){
					sum+=j;
				}
			}
			cout << "Case " << i << ": " << sum << endl;
			sum=0;
			 
		}
	}
}