修改为斐波那契数列的最少次数

解题思路:

实际上由输入的数列变化得到的斐波那契数列必然是首项为1的斐波那契数列的倍数，只需要对比输入数列的每一个元素与首项1的斐波那契数列的倍数关系，找到出现的倍数关系次数最多的数，将其他不是该倍数关系的数进行更改，就是答案。

注意事项:注意开long long 

参考代码:

#include

using namespace std;

#define LL long long

const int N=1e6+5;

LL t[N],f[N];

int n;

LL num,maxnum=0;

int ans=0x7ffffff;

int main()

{

    cin>>n;

    f[0]=f[1]=1;

    for(int i=2;i<n;i++)

        f[i]=f[i-1]+f[i-2]; //以1为首项的斐波那契数列

    for(int i=0;i<n;i++)

    {

        cin>>num;

        maxnum=max(maxnum,num);//找到数列中最大的数

        int k=num%f[i];//对比是否为倍数

        if(k==0)

            t[num/f[i]]++;相同倍数的

    }

LL tmnum=0;

for(int i=1;i<=maxnum;i++)

    tmnum=max(tmnum,t[i]);//找到相同倍数的数最多的个数

ans=n-tmnum;

cout<<ans;

    return 0;

}