7-大数斐波那契额数列

链接：https://www.nowcoder.net/acm/contest/71/C
来源：牛客网

时间限制：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

输入

输出

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

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
string a[100005];

string sum(string s1,string s2){  //大数加法（string + string, return string）
    if(s1.length()<s2.length())
    {
        string temp=s1;
        s1=s2;
        s2=temp;
    }
    int i,j;
    for(i=s1.length()-1,j=s2.length()-1;i>=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
", x);
	}
	
	return 0;
}

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

#include <bits/stdc++.h>
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 <bits/stdc++.h>
using namespace std;
#define ll long long
#define clr(a,b) memset(a,b,sizeof(a))
const ll mod=1000000007;
map<ll,int>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<<m[tp]<<'
';
    }
}