1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103
| #include<stdio.h> #include<set> #include<iostream> #include<stack> #include<cstring> #include<cmath> #include<vector> #include<map> #include<queue> #include<algorithm> typedef long long ll; typedef long double ld; typedef double db; #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; const int mod=1e9+7; inline int mo(ll a,int p){ return a>=p?a%p:a; } inline int rd() { int x = 0, f = 1; char ch; while (ch < '0' || ch > '9') { if (ch == '-')f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return f * x; } inline ll gcd(ll x, ll y){ return y==0?x:gcd(y,x%y); } inline ll speed(ll a,ll b){ ll cur=a,anss=1; while(b){ if(b&1) anss=anss*cur; cur=cur*cur; b>>=1; } return anss; } const int MAXN=1e5; bool ipr[MAXN+20]; int cnt,pri[MAXN/5]; void prime(){ int N=sqrt(MAXN)+0.5,mul; memset(ipr,true,sizeof(ipr)); ipr[1]=false; for(int i=2;i<=N;i++){ if(ipr[i]==true){ i==2?mul=1:mul=2; for(int j=i*i;j<=MAXN;j+=i*mul){ ipr[j]=false; } } } for(int i=2;i<=MAXN;i++){ if(ipr[i]==true){ pri[++cnt]=i; } } } int T; ll n; ll fib[120]={1,1},sfib[120]={0,1}; ll sum[120]={0,1,3},ssum[120]={0,1,4}; ll dfs(ll layer,ll cur){ if(layer<=0||cur<=0) return 0; if(cur==fib[layer]) return sum[layer]; if(cur<=fib[layer-1]) return dfs(layer-1,cur); return sum[layer-1]+dfs(layer-2,cur-fib[layer-1])+cur-fib[layer-1]; } int main(){ for(int i=2;i<=91;i++){ fib[i]=fib[i-1]+fib[i-2]; sfib[i]=sfib[i-1]+fib[i]; } for(int i=3;i<=91;i++){ sum[i]=sum[i-1]+sum[i-2]+fib[i-2]; ssum[i]=ssum[i-1]+sum[i]; } scanf("%d",&T); while(T--){ scanf("%lld",&n); n--; ll ans=1,cur=n; ll p=lower_bound(sfib+1,sfib+1+81,cur)-sfib-1; cur-=sfib[p]; ans+=ssum[p]; p++; ans+=dfs(p,cur); printf("%lld\n",ans); } return 0; }
|