C++11(clang++ 3.9) 解法, 执行用时: 10ms, 内存消耗: 1272K, 提交时间: 2019-03-09 22:17:34

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int mymax(int x,int y) {return x>y?x:y;}

struct hugeint
{
    int a[110],l;
    void clear()
    {
        memset(a,0,sizeof(a));
        l=1;
    }
    friend hugeint operator + (hugeint x,hugeint y)
    {
        int ll=mymax(x.l,y.l);
        for(int i=1;i<=ll;i++) x.a[i]=x.a[i]+y.a[i];
        for(int i=1;i<=ll;i++) x.a[i+1]+=x.a[i]/10,x.a[i]%=10;
        while(x.a[ll+1]!=0) x.a[ll+2]+=x.a[ll+1]/10,x.a[ll+1]%=10,ll++;
        x.l=ll;
        return x;
    }
    friend hugeint operator + (hugeint x,int y)
    {
        int ll=x.l;  x.a[1]+=y;
        for(int i=1;i<=ll;i++) x.a[i+1]+=x.a[i]/10,x.a[i]%=10;
        while(x.a[ll+1]!=0) x.a[ll+2]+=x.a[ll+1]/10,x.a[ll+1]%=10,ll++;
        x.l=ll;
        return x;
    }
    friend hugeint operator / (hugeint x,int y)
    {
        int nw=0;
        for(int i=x.l;i>=1;i--)
        {
            nw=nw*10+x.a[i];
            x.a[i]=nw/y;
            nw%=y;
        }
        while(x.a[x.l]==0&&x.l>1) x.l--;
        return x;
    }
};

hugeint k1,k2;
void dfs(hugeint xx)
{
    if(xx.l==1&&xx.a[1]==1)
    {
        k1=xx;k2.clear();
        return;
    }
    dfs((xx+1)/2);
    if(xx.a[1]&1) k1=k1+k2;
    else k2=k1+k2;
}

char s[110];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s+1);
        int l=strlen(s+1);
        hugeint xx;xx.clear();
        for(int i=1;i<=l;i++) xx.a[l-i+1]=s[i]-'0';
        xx.l=l;
        dfs(xx);
        for(int i=k1.l;i>=1;i--) printf("%d",k1.a[i]);
        printf("\n");
    }
    return 0;
}

Java(javac 1.8) 解法, 执行用时: 147ms, 内存消耗: 21200K, 提交时间: 2019-08-27 18:15:47

//package qwq;
import java.math.*;
import java.util.*;
public class Main {
    public static BigInteger dfs(BigInteger x1,BigInteger a,BigInteger x2,BigInteger b){
        if(x1.compareTo(BigInteger.ONE)==0) return a.add(b);
        if(x1.mod(new BigInteger("2")).compareTo(BigInteger.ZERO)==0)
            return dfs(x1.divide(new BigInteger("2")),a.add(b),x1.divide(new BigInteger("2")).add(BigInteger.ONE),b);
        return dfs(x2.divide(new BigInteger("2")).subtract(BigInteger.ONE),a,x2.divide(new BigInteger("2")),a.add(b));

    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int t; t=sc.nextInt();
        while(t-->0){
            BigInteger n=sc.nextBigInteger();
            if(n.compareTo(BigInteger.ZERO)==0){
                System.out.println('0'); continue;
            }
            while(n.mod(new BigInteger("2")).compareTo(BigInteger.ZERO)==0){
                n=n.divide(new BigInteger("2"));
            }
            BigInteger tt=n.divide(new BigInteger("2"));
            if(tt.compareTo(BigInteger.ZERO)==0){
                System.out.println('1'); continue;
            }
            BigInteger ans=dfs(tt,BigInteger.ONE,tt.add(BigInteger.ONE),BigInteger.ONE);
            System.out.println(ans);
        }
    }
}

Python(2.7.3) 解法, 执行用时: 38ms, 内存消耗: 3064K, 提交时间: 2019-08-27 17:56:10

def dfs(a,na,b,nb):
    if (a==1):
	    return na+nb
    if (a%2==0):
	    return dfs(a//2,na+nb,a//2+1,nb)
    return dfs(b//2-1,na,b//2,na+nb)
T=raw_input()
T=int(T)
while (T>0):
    T-=1
    n=raw_input()
    n=long(n)
    if (n==0):
	    print 0
	    continue
    while (n%2==0):
        n//=2
    x=n//2
    if (x==0):
        print 1
    else:
        print dfs(x,1,x+1,1)

Python3(3.5.2) 解法, 执行用时: 32ms, 内存消耗: 3688K, 提交时间: 2019-08-27 18:09:16

def dfs(x1,a,x2,b):
    if (x1==1):
	    return a+b
    if (x1%2==0):
	    return dfs(x1//2,a+b,x1//2+1,b)
    return dfs(x2//2-1,a,x2//2,a+b)
t=int(input())
while (t>0):
    t-=1
    n=int(input())
    if (n==0):
	    print("0")
	    continue
    while (n%2==0):
        n//=2
    x=n//2
    if (x==0):
        print("1")
    else:
        print(dfs(x,1,x+1,1))