c777 - 106北二2.規律的數列
題目描述
題目要求計算在給定的範圍 [n, m] 內，屬於特定規律數列的數字個數。該數列的定義是：前三項為 0, 1, 2，後續每一項等於前三項的和。
解題思路
此題的解題思路是先預先計算出數列的足夠多項，儲存在陣列中。然後，對於每組輸入的 n 和 m，遍歷預先計算的數列，統計落在 [n, m] 範圍內的數字個數。由於題目中 n 和 m 的最大值為 10^18，直接計算數列的每一項可能會導致溢位。然而，題目範例和輸出表明，數列的增長速度很快，且所需的數列項數相對較少。因此，預先計算數列的前 70 項是足夠的。
複雜度分析
- 時間複雜度: O(70 + Q)，其中 Q 是輸入的組數。預先計算數列需要 O(70) 的時間，對於每組輸入，遍歷數列需要 O(70) 的時間。
- 空間複雜度: O(70)，用於儲存預先計算的數列。
程式碼
#include <iostream>
using namespace std;
//1000000000000000000
//152074750075811746
int main(){
long long int a[1000]={},a1=0,a2=1,a3=2,t=0,x,y;
a[0]=0;
a[1]=1;
a[2]=2;
for(long long int i=3;i<70;i++){
t=a1+a2+a3;
a1=a2;
a2=a3;
a3=t;
a[i]=t;
}
while(cin >> x >> y){
int ans=0;
for(int i=0;i<70;i++){
if((a[i]<=y&&a[i]>=x)||(a[i]>=y&&a[i]<=x))
ans++;
}
cout << ans << endl;
}
}