## Editorial for Fibonacci Sequence

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của RR

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;

const double PI = acos(-1.0);

ll fib[91], f[71][2], g[71][2];
int save[70];

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
fib[0] = fib[1] = 1;
FOR(i,2,90) fib[i] = fib[i-1] + fib[i-2];

f[1][0] = f[1][1] = 1;
FOR(i,2,70) {
f[i][0] = f[i-1][0] + f[i-1][1];
f[i][1] = f[i-1][0];
}

g[1][0] = 0; g[1][1] = 1;
FOR(i,2,70) {
g[i][0] = g[i-1][0] + g[i-1][1];
g[i][1] = g[i-1][0] + f[i][1];
}

ll len = 0, nBit = 0, n, res = 0; cin >> n;

while (nBit < n) {
len++; nBit += f[len][1] * len;
res += g[len][1];
}
res -= g[len][1]; nBit -= f[len][1] * len;

//    cout << res << ' ' << nBit << ' ' << len << endl;

ll diff = 0;
ll u = (n - nBit) / len;
if ((nBit - n) % len) { u++; diff = (nBit + u * len) - n; }

//    cout << u << ' ' << diff << endl;

int l = len;
save[1] = 1; res += u;
//    cout << res << endl;
FOR(now,2,len) {
l--;
if (f[l][0] >= u) {
save[now] = 0;
}
else {
save[now] = 1;
u -= f[l][0];
res += u + g[l][0];
}
}
//    FOR(x,1,len) cout << save[x]; cout << endl;
FORD(x,len,len-diff+1) res -= save[x];
cout << res << endl;
return 0;
}


#### Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>

long long a[200],f[200],u[200];

long long xuly(long long n)
{
//int flag = 0;
for(int i = 1;;i++)
{
if(a[i]==n)
return f[i];
else if(a[i]>n)
return f[i-1]+xuly(n-a[i-1])+n-a[i-1];
}

}

int main()
{
long long Nmax = 1; for(int i = 1;i<=15;i++) Nmax = Nmax*10;
a[1] = 1; a[2] = 2; f[1] = 1; f[2] = 2; u[1]=1; u[2] = 3;
for(int i = 3;;i++)
{
a[i] = a[i-1]+a[i-2];
f[i] = a[i]-a[i-1]-1+f[i-2]+f[i-1];
u[i] = u[i-1]+(i-1)*(a[i]-a[i-1])+1;
if(a[i]>Nmax)
break;
}
long long n,KQ = 0;
int flag = 0;
scanf("%lld",&n);
for(int i = 1;;i++)
{
if(u[i]>n)
{
flag = i-1;
break;
}
}
long long N = (n-u[flag])/flag+a[flag];
KQ = xuly(N);
long long m =  (n-u[flag])%flag;
long long M = N+1;
for(int i = 1;;i++)
{
if(a[i]>M)
{
for(int j = 1;j<=m;j++)
{
if(M==0)
break;
else if(M>=a[i-j])
{
M = M-a[i-j];
KQ++;
}
}
break;
}
}
printf("%lld",KQ);
// getch();
}


#### Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

long long L,cnt,ret;
long long num[105],fibo[105],numOne[105];

string convert(long long x)
{
if (x < 2) return "0";
for (int i = 0; ; i++) if (fibo[i] > x)
{
string ans = "";
for (int j = i - 1; j; j--) if (x >= fibo[j])
{
x -= fibo[j];  ans += '1';
}
else ans += '0';
return ans;
}
}

{
if (x <= 0) return 0;
if (x == 1) return 1;
long long sum = 0;
for (int i = 0; ; i++)
if (sum + num[i] <= x) sum += num[i];
else return numOne[i - 1] + (x - sum + 1) + add(x - sum);
}

int main()
{
//freopen("fibo.in","r",stdin);

fibo[0] = fibo[1] = 1;
for (int i = 2; i <= 95; i++) fibo[i] = fibo[i - 1] + fibo[i - 2];
num[0] = num[1] = 1;

numOne[0] = 0;  numOne[1] = 1;

while (cin >> L)
{
if (L < 1)
{
printf("0\n");  continue;
}
if (L < 2)
{
printf("1\n");  continue;
}

L--;  ret = 1;
for (int i = 2; ; i++)
{
num[i] = cnt = fibo[i - 1];
numOne[i] = numOne[i - 1] + numOne[i - 2] + cnt;
if (L/cnt >= i)
{
L -= 1LL * cnt * i;  ret += cnt + numOne[i - 2];
}
else
{
long long addmore = L/i;  L %= i;
if (L)
{
long long sum = 0;
for (int j = 1; j < i; j++) sum += num[j];
string parse = convert(sum + addmore + 1);
for (int j = 0; j < L; j++) if (parse[j] == '1') ret++;
}
break;
}
}
printf("%lld\n", ret);
}
}