XTU 1387 完全区间

题目描述

序列X由线性产生式 xn=axn−1+bxn−2,x0=x1=1 产生，
序列Y由线性产生式 yn=cyn−1+dyn−2,y0=y1=1 产生，
集合Z={x+y∣x∈X,y∈Y}。
现有区间[L,R]，求最长的子区间[l,r],满足L≤l≤r≤R,∀z∈[l,r],z∈Z。

输入格式

第一行是一个整数T(1≤T≤1000)，表示样例的个数。 每个样例占一行，为6个整数，a,b,c,d,L,R,其中1≤a,b,c,d,L,R≤10^9

输出格式

依次每个样例，输出最长的子区间的长度，为一个整数。 如果不存在这样的区间，输出0。

样例输入

3
1 1 1 1 1 10
1 1 1 1 1 15
1 1 1 1 12 12

样例输出

9
10
0

样例解释

样例中X和Y都是斐波那契数列，所以集合Z={2,3,4,5,6,7,8,9,10,11,13,14,15,…}。

思路：求出数组X，数组Y，数组Z，再求出区间长度，结合我的代码来很好理解，这也是参考了一下大佬的代码TAT，不然死活不知道自己错在哪。

AC代码：

#include 
#include 
#include 
#include 
#define N 1000000000
__int64 cmp(void* a,void* b){return *(__int64*)a-*(__int64*)b;
}
int main()
{int n;scanf("%d",&n);while(n--){__int64 a,b,c,d,L,R,res=0;scanf("%I64d%I64d%I64d%I64d%I64d%I64d",&a,&b,&c,&d,&L,&R);__int64 i,j;__int64 x[100],y[100],z[3000],z1[3000];//z数组表示x数组+y数组，z1表示z数组去重之后的数组。memset(x,0,sizeof(x));memset(y,0,sizeof(y));memset(z,0,sizeof(z));memset(z1,0,sizeof(z1));x[0]=1,x[1]=1;y[0]=1,y[1]=1;__int64 l1=1,l2=1;for(i=2;i<57;i++){x[i]=a*x[i-1]+b*x[i-2];l1++;if(x[i]<=0||x[i]>=N)//小于等于0是防止溢出，因为题目给的是10的9次方，这么多循环够了。break;;}for(i=2;i<57;i++){y[i]=c*y[i-1]+d*y[i-2];l2++;if(y[i]<=0||y[i]>=N)break;}for(i=0;i<=l1;i++)//求z{for(j=0;j<=l2;j++){if(L<=x[i]+y[j]&&x[i]+y[j]<=R)z[res++]=x[i]+y[j];}}if(res==0){//注意，这一步必不可少，上次我就是少了这一步，死活过不了，读者可以去尝试一下。printf("0\n");}else{qsort(z,res,sizeof(__int64),cmp);//快排，排序z1[0]=z[0];int rnt=0;for(i=1;imax){max=length;}}else{length=1;}}printf("%I64d\n",max);}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！