7-大数斐波那契额数列-白红宇

7-大数斐波那契额数列

阅读量：5063 次

发布时间：2019-06-12

本文共 2872 字，大约阅读时间需要 9 分钟。

链接：

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

小W在计算一个数列{A

_n},其中A

₁=1,A

₂=2,A

_n+2=A

_n+1+A

_n。尽管他计算非常精准，但很快他就弄混了自己的草稿纸，他找出了一些他计算的结果，但他忘记了这些都是数列中的第几项。

输入描述:

每行包括数列中的一项A_k(k<=100000)。

总行数T<=30。

输出描述:

对于每一项A_k，输出一行包括一个正整数k表示输入中数是数列的第几项。

示例1

输入

输出

23456 并没有ac的答案：先用大数加法，求出每个数，在对输入的数用二分查找--->超时

#include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;string a[100005];string sum(string s1,string s2){  //大数加法（string + string, return string）    if(s1.length()
              
               =0;i--,j--)    {        s1[i]=char(s1[i]+(j>=0?s2[j]-'0':0));   //注意细节        if(s1[i]-'0'>=10)        {            s1[i]=char((s1[i]-'0')%10+'0');            if(i) s1[i-1]++;            else s1='1'+s1;        }    }    return s1;}void db(){	a[1] = "1";	a[2] = "2";		for(int i = 3; i <= 10000; i++){		a[i] = sum(a[i - 1], a[i - 2]);	}	cout << a[200] << endl;}int bSearch(int begin, int end, string e)      //二分查找string数组中的目标串{        int mid, left = begin, right = end;       while(left <= right)        {            mid = (left + right) >> 1;            if(a[mid] == e) 　　　　　　　return mid;	else if(a[mid].length() > e.length()) //根据string重载<>的的特点，我没要先按长度排序	　　right = mid - 1;            else if(a[mid].length() < e.length()) 	　　left = mid + 1;　　　　 else if(a[mid] > e)	　　right = mid - 1;　　　 　else if(a[mid] < e)	   left = mid + 1;        }        return left;    }  int main(){	db();	string str;	while(cin >> str){		int x = bSearch(0, 30000, str);		printf("%d\n", x);	}		return 0;}

　　附上ac代码：居然可以取模来离散一下，还是题目做少了，赶紧刷题去：

#include 
          
           using namespace std;typedef long long ll;const ll mod = 1e9+7;ll a[100005] = {0, 1, 2};int main(){	string str;	for(int i = 3; i <= 100000; i++){		a[i] = (a[i - 1] + a[i - 2]) % mod;	}		while(cin >> str){		ll fn = 0;		for(int i = 0; i < str.length(); i++){			fn = (fn * 10 + str[i] - '0') % mod;		}			for(int i = 1; i <= 100000; i++){			if(fn == a[i]){				cout << i << endl;				break;			}		}	}		return 0;} #include 
           
            using namespace std;#define ll long long#define clr(a,b) memset(a,b,sizeof(a))const ll mod=1000000007;map
            
             m;  //用了map，方便查询，可是好像没有直接暴力搜块 ll a[100001];int main(){    a[1]=1,a[2]=2;    m[1]=1,m[2]=2;    for (int i = 3; i < 100001; ++i)    {        a[i]=(a[i-1]%mod+a[i-2]%mod)%mod;        m[a[i]]=i;    }    string s;    while(cin>>s)    {        int l=s.length();        ll tp=0;        for (int i = 0; i < l; ++i)        {            tp*=10;            tp%=mod;            tp+=(s[i]&15);            tp%=mod;        }        cout<
             
              <<'\n';    }}