d186 - 11461 - Square Numbers
題目描述
題目要求計算給定區間 [a, b] 內完全平方數的個數。
解題思路
題目要求計算區間內的完全平方數，可以透過迭代的方式找出區間內的完全平方數。首先，找到大於等於 a 的最小完全平方數，然後不斷計算下一個完全平方數，直到超過 b 為止。每次計算到一個完全平方數，就將計數器加一。
複雜度分析
- 時間複雜度: O(sqrt(b))
- 空間複雜度: O(1)
程式碼
#include <iostream>
#include <math.h>
using namespace std;
int main(){
long long int a=0,b=0,c=1,ans=0;
while(cin >> a >> b){
if(a>0||b>0){
while(c*c<a){
c++;
}
while(c*c<=b){
c++;
ans++;
}
cout << ans << endl;
ans=0;
c=0;
}
}
}