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;
}