C++11(clang++ 3.9) 解法, 执行用时: 263ms, 内存消耗: 2244K, 提交时间: 2020-08-28 18:57:46

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define inf 1000000000
#define rad 100000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char tmp[10005];
string ch;
int bin[20];
struct data{
    int l;ll v[2005];
    data(){
        l=1;
        memset(v,0,sizeof(v));
    }
    inline ll& operator[](int x){ 
        return v[x];
    }
    friend data operator+(data a,data b){
        if(a.l<b.l)swap(a,b);
        for(int i=1;i<=b.l;i++)
            a[i]+=b[i];
        for(int i=1;i<=a.l;i++)
            if(a[i]>=rad)
            {
                if(i==a.l)a.l++;
                a[i+1]+=a[i]/rad;
                a[i]%=rad;
            }
        return a;
    }
    friend data operator*(data a,data b){
        data c;
        for(int i=1;i<=a.l;i++)
            for(int j=1;j<=b.l;j++)
                c[i+j-1]+=a[i]*b[j];
        for(int i=1;i<=a.l+b.l;i++)
        {
            if(c[i]>=rad)
            {
                c[i+1]+=c[i]/rad;
                c[i]%=rad;
            }
            if(c.v[i])c.l=i;
        }
        return c;
    }
    friend void print(data a){
        for(int i=a.l;i;i--)printf("%.8I64d",a[i]);
        puts("");
    }
    friend bool operator<=(data a,data b){
        if(a.l<b.l)return 1;
        else if(a.l>b.l)return 0;
        for(int i=a.l;i;i--)
            if(a[i]<b[i])return 1;
            else if(a[i]>b[i])return 0;
        return 1;
    }
}n;
data get(string ch){
    data a;
    int t=ch.length();ch=" "+ch;
    a.l=(t-1)/8+1;
    for(int i=1;i<=a.l;i++)
    {
        ll k=1;
        for(int j=1;j<=8;j++)
        {
            if(t-8*(i-1)-j+1>=1)
                a[i]+=k*(ch[t-8*(i-1)-j+1]-'0');
            k*=10;
        }
    }
    return a;
}
struct M{
    data v[2][2];
    friend M operator*(M a,M b){
        M c;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                for(int k=0;k<2;k++)
                    c.v[i][j]=c.v[i][j]+(a.v[i][k]*b.v[k][j]);
        return c;
    }
}t[20],a;
int main(){
    bin[0]=1;for(int i=1;i<=15;i++)bin[i]=bin[i-1]<<1;
    t[0].v[0][0]=t[0].v[0][1]=t[0].v[1][0]=get("1");
    for(int i=1;i<=15;i++)
        t[i]=t[i-1]*t[i-1];
    int T=read();
    while(T--){  
        a.v[0][0]=a.v[1][1]=get("1");
        a.v[1][0]=a.v[0][1]=get("0");
        scanf("%s",tmp);
        int len=strlen(tmp);
        ch="";
        for(int i=0;i<len;i++)ch+=tmp[i];
        if(len==1&&ch[0]=='6'){puts("0");continue;}
        n=get(ch)+get("1");
        int now=0;
        for(int i=15;i>=0;i--){
            M tmp=a*t[i];
            if(tmp.v[0][0]<=n)
                a=tmp,now+=bin[i];
        }
        printf("%d\n",(now-2)/2);
    }
    return 0;
}