P8808 [蓝桥杯 2022 国 C] 斐波那契数组

· · 个人记录 


/*
根据费波纳的特点，到int只有47个数据。
数列的特点，确定了开头就可以确定结尾。
数列是fibon的比例数列。计算位置与比例关系即可。
根据题目的数据范围，
*/
#include<bits/stdc++.h>
using namespace std;
typedef long  long ll;
const int N=2e5+9;
const int inf=1e6;
int n,f[45],a[N],b[45];
int main(){
    f[0]=f[1]=1; 
    for(int i=2;i<=44;i++){
        f[i]=f[i-2]+f[i-1];

    }
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];

    }
    int m=n;
    for(int i=0;i<n;i++){
        if(a[i]%f[i]==0)b[i]=a[i]/f[i];
        if(f[i]>inf){m=i;break;}
    }
    sort(b,b+m);
    int ans=n,len=1;
    for(int i=0;i<m;i++){
    //  cout<<b[i]<<" ";
            if(b[i]==0)continue;
            if(b[i]==b[i-1])len++;
                else ans=min(ans,n-len),len=1;  
    }
    cout<<ans<<endl;

}