HPU1471又是斐波那契数列？？

迷南。 2022-05-18 04:23 179阅读 0赞

1471: 又是斐波那契数列？？  
时间限制: 1 Sec 内存限制: 128 MB

提交: 338 解决: 44 统计  
**题目描述**  
大家都知道斐波那契数列吧？斐波那契数列的定义是这样的： f0 = 0; f1 = 1; fi = fi-1 + fi-2

现在给你一个数x，聪明的你一定知道这是斐波那契数列中的第几项。  
(数据保证x一定有对应的项y，且 0 <= y < 1e4)

**输入**  
第一行一个整数T，表示测试组数。  
之后的T行，每行一个数x  
**输出**  
对于每个测试数据，输出一行表示数x是第几项  
**样例输入**  
2  
2  
5  
**样例输出**  
3  
5  
**来源**  
李战士

--------------------

打表，大数取模，可是教的时候WA了好多次，今天问了下队友，他说要从2开始找  
我打的表是从0开始往前找的，f\[1\]=1,f\[2\]=1  f \[ 1 \] = 1 , f \[ 2 \] = 1  所以这就很尴尬了，我输入1，输出也是1，但是结果是应该是2，这个坑好…..

--------------------

我的AC代码

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const LL mod=1e16+7;
    const int MAXN=1e4+9;
    LL f[MAXN];
    char s[100000];
    void init()
    {
        f[0]=0;
        f[1]=1;
        for(int i=2;i<MAXN;i++)
            f[i]=(f[i-1]%mod+f[i-2]%mod)%mod;
    }
    int main()
    {
        init();
        int t;
        scanf("%d",&t); 
        while(t--)
        {
            scanf("%s",s);
            int len=strlen(s);
            LL ans=0;
            for(int i=0;i<len;i++)
                ans=((ans*10)%mod+s[i]-'0')%mod;
            int x; 
            for(int i=2;i<MAXN;i++)
                if(ans==f[i])
                {
                    x=i;
                    break;  
                }   
            printf("%d\n",x);
        }
        return 0;
    }

队友的AC代码，用map存储的表，效率比较高

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const LL mod=1e16+7;
    const int MAXN=1e4+9;
    LL f[MAXN];
    char s[100000];
    int main()
    {
        map<LL,int> m;
        f[0]=0;
        f[1]=1;
        for(int i=2;i<MAXN;i++)
        {
            f[i]=(f[i-1]%mod+f[i-2]%mod)%mod;
            m[f[i]]=i;
        }
        int t;
        scanf("%d",&t); 
        while(t--)
        {
            scanf("%s",s);
            int len=strlen(s);
            LL ans=0;
            for(int i=0;i<len;i++)
                ans=(ans*10+s[i]-'0')%mod;          
            printf("%d\n",m[ans]);
        }
        return 0;
    }