## Editorial for VOI 12 Bài 4 - Bản vanxơ Fibonacci

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 flashmt

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

int f[20]={0,1,2};

int cyclic(int u,int v)
{
int l=v-u+1;
for (int x=1;x<=l/2;x++)
if (l%x==0)
{
int ok=1;
for (int i=u+x;i<=v;i++)
if (f[i%16]!=f[(i-x)%16])
{
ok=0; break;
}
if (ok) return 1;
}
return 0;
}

int calc(int u,int v)
{
int res=-1;
if (v-u+1<=100)
{
for (int i=u;i<v;i++)
for (int j=i+1;j<=v;j++)
if (cyclic(i,j))
res=max(res,j-i+1);
}
else res=(v-u+1)/16*16;
return res;
}

int main()
{
int test,u,v;
for (int i=3;i<=16;i++) f[i%16]=(f[i-1]+f[i-2])%7;

cin >> test;
while (test--) cin >> u >> v, cout << calc(u,v) << endl;
}


#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#include <climits>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define RESET(a, v) memset((a), (v), sizeof((a)))
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>

using namespace std;
int f[111];
int k;
LL u, v;

int main() {
ios :: sync_with_stdio(0); cin.tie(0);
f[0] = 1; f[1] = 2;
FOR(i, 2, 100) f[i] = (f[i - 1] + f[i - 2]) % 7;
cin >> k;
while (k--) {
cin >> u >> v;
u--; v--;
LL len = v - u + 1, ans = -1;
if (len >= 32) ans = len / 16 * 16;
else {
u %= 32;
FOR(i, u, u + len - 1)
if (f[i] == f[i + 1]) ans = 2;
}
cout << ans << '\n';
}
return 0;
}


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

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

#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = a; i >= b; --i)
#define REP(i,a) for(int i = 0; i < a; ++i)
#define MP make_pair
#define PB push_back

#define DEBUG(x) { cout << #x << " = "; cout << x << endl; }
#define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
#define PR0(a,n) { cout << #a << " = "; REP(_,0,n) cout << a[_] << ' '; cout << endl; }

using namespace std;

int f[111];
int canDivide[111][111][111], good[111][111], best[111][111];

// canDivide(i,j,x) = can divide (i,j) to equal segments of length x
// good(i,j) = can divide(i,j) to k equals segment, for some k
// best(i,j) = longest good subsequence

int same(int i, int j, int len) {
while (len--) {
if (f[i++] != f[j++]) return 0;
}
return 1;
}

void init() {
f[1] = 1; f[2] = 2;
FOR(i,3,100) f[i] = (f[i-1] + f[i-2]) % 7;
//    PR(f, 100);

FORD(i,100,1) FOR(j,i,100) {
int len = j - i + 1;
FOR(each,1,len-1) {
if (len % each != 0) canDivide[i][j][each] = 0;
else {
int k = len / each;
if (k == 2) canDivide[i][j][each] = same(i,i+each,each);
else canDivide[i][j][each] = canDivide[i][j-each][each] && canDivide[i+each][j][each];
}
if (canDivide[i][j][each]) good[i][j] = 1;
}
}

FORD(i,100,1)
FOR(j,i,100) {
if (good[i][j]) best[i][j] = j - i + 1;
else best[i][j] = max(best[i+1][j], best[i][j-1]);

if (best[i][j] == 0) best[i][j] = -1;
}
}

int solve(int u, int v) {
int res = -1;
int len = (v - u + 1);
if (len >= 32) res = (len / 16) * 16;
else {
int saveu = u, savev = v;
if (len >= 9) res = 2;
while (v % 8 != 1) --v;
while (u % 8 != 0) ++u;
if (u <= v) res = 2;

u = saveu; v = savev;
}

return res;
}

int main() {
//    init();

int ntest; scanf("%d", &ntest);
while (ntest--) {
int u, v; scanf("%d%d", &u, &v);
printf("%d\n", solve(u, v));
}
return 0;
}


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

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define ep 0.00001
#define maxn 1011
#define oo 2000000001
#define modunlo 111539786
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define fi first
#define se second
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

int test,u,v,n;

int main(){
// freopen("input.in","r",stdin);
//freopen("output.out","w",stdout);

int x[] = {1, 2, 3, 5, 1, 6, 7, 6, 6, 5, 4, 2, 6, 1, 7, 1, 1, 2, 3, 5, 1, 6, 7, 6, 6, 5, 4, 2, 6, 1, 7, 1, 1, 2, 3, 5, 1, 6, 7, 6, 6, 5, 4, 2, 6, 1, 7, 1};

scanf("%d",&test);
for(int itest = 1; itest <= test; itest++){
scanf("%d %d",&u,&v);
n = v - u;
if( n > 30){
printf("%d\n",((n+1)/16)*16);
}
else{
int t = (u-1)%16;
bool flag = true;
for(int i = t; i < t+n; i++){
if(x[i] == x[i+1]){
printf("2\n");
flag = false;
break;
}
}
if(flag) printf("-1\n");
}
}
}


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

#include<cstdio>
const int res[]={0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1};
int fib(const int &x) {
return (res[(x+1)%16]);
}
int count(const int &u,const int &v) {
if (v-u+1>=32) return (((v-u+1)/16)*16);
int i;
for (i=u;i<v;i=i+1)
if (fib(i)==fib(i+1)) return (2);
return (-1);
}
int c,u,v,t;
int main(void) {
scanf("%d",&t);
for (c=1;c<=t;c=c+1) {
scanf("%d",&u);
scanf("%d",&v);
printf("%d\n",count(u,v));
}
return 0;
}