首页 > 代码库 > 对你的爱深不见底
对你的爱深不见底
对你的爱深不见底
这题的话,其实可以先打个表找一下规律,然后会发现,n是没什么卵用的,你只要关注m就行了.然而,m很大很大很大,不得不开高精,这就为解题带来了麻烦.
我们先把答案的序列打出来:
乍一看,很有规律的样子(别说你没看出来).我们再细分一下:
我们发现,划分成的子区间都是公差为1的等差数列,且区间长都是fib数.我们在观察一下:
我们发现,每个区间的第一行元素+1也是fib数!
那么,如果我们知道一个数m,我们要知道ans,我们可以通过两个fib数列推出!
我们先可以求出m>sum(fib[1~i])(fib[1]=1,fib[2]=2)中i的最大值.也就是说,我们已经推到了数m对应ans所在的区间的上一个区间的末行.
而且,我们又可以在同时求出ans所在区间的第一行的元素,那么我们就可以轻松知道ans了.
我们设数m对应ans所在的区间的上一个区间的末行的元素为x,ans所在区间的第一行的元素为y
则ans=y+m-x-1.(可以自己去推一推)
最后,注意输出的数要对那个万恶的数(为什么万恶?额,没什么)取模再输出.
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #define LL long long 5 using namespace std; 6 const int maxl=1005; 7 const int TT=258280327; 8 int n,ans; 9 struct bigint{10 int len,a[maxl];11 bigint(){len=0,memset(a,0,sizeof a);}12 void read(){13 char c[maxl]; scanf("%s",c);14 len=strlen(c); for (int i=1; i<=len; i++) a[i]=c[i-1]-‘0‘;15 for (int i=1; i<=len/2; i++) swap(a[i],a[len-i+1]);16 }17 bigint operator + (const bigint b){18 bigint c; c.len=max(len,b.len);19 for (int i=1; i<=c.len; i++){20 c.a[i]+=a[i]+b.a[i];21 c.a[i+1]=c.a[i]/10;22 c.a[i]%=10;23 }24 while (c.a[c.len+1]) c.len++;25 return c;26 }27 bigint operator - (const bigint b){28 bigint c; c.len=len;29 for (int i=1; i<=c.len; i++){30 c.a[i]+=a[i]-b.a[i];31 if (c.a[i]<0) c.a[i]+=10,c.a[i+1]--;32 c.a[i+1]+=c.a[i]/10;33 c.a[i]%=10;34 }35 while (c.len>1&&!c.a[c.len]) c.len--;36 return c;37 }38 bool operator > (const bigint b){39 if (len>b.len) return 1; else if (len<b.len) return 0;40 for (int i=len; i; i--) if (a[i]>b.a[i]) return 1;41 else if (a[i]<b.a[i]) return 0;42 return 0;43 }44 void write(){45 for (int i=len; i>=1; i--) a[i-1]=(a[i-1]+(LL)a[i]*10%TT)%TT;46 printf("%d",a[1]); putchar(‘\n‘);47 }48 }m,x,y,z,a,b,c,final,dif,one,tot;49 int main(){50 int T; cin>>T; one.len=1,one.a[1]=1;51 for (; T; T--){52 cin>>n,ans=0,m.read();53 if (m.len==1&&m.a[1]<7){54 if (m.a[1]==1) puts("0"); else55 if (m.a[1]==2) puts("0"); else56 if (m.a[1]==3) puts("1"); else57 if (m.a[1]==4) puts("1"); else58 if (m.a[1]==5) puts("2"); else59 if (m.a[1]==6) puts("3");60 continue;61 }62 m=m-one;63 x.len=1,x.a[1]=2,y.len=1,y.a[1]=3,z=x+y;64 a.len=1,a.a[1]=1,b.len=1,b.a[1]=2,c=a+b;65 tot=z;66 while (m>tot){67 c=a+b; a=b; b=c;68 final=tot+z;69 if (!(m>final)){final=tot; break;} else tot=final;70 x=y; y=z; z=x+y;71 }72 dif=m-final;73 c=c-one; final=c+dif; final=final-one;74 final.write();75 }76 return 0;77 }
对你的爱深不见底
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。