求大神关于C++斐波那契数列整除问题

求大神关于C++斐波那契数列整除问题
问题描述  已知四个数:a,b,c,d,判断在第s个Fibonacci数到第t个Fibonacci数之间哪些数既不是a也不是b也不是c也不是d的倍数.输入格式  第一行两个数,s,t,表示要判断第s个Fibonacci数到第t个Fibonacci数之间(包含第s个和第t个)的Fibonacci数.
  第二行四个数,a,b,c,d,意义如题目描述.输出格式  一行若干个数,A1,A2,A3...An,从小到大排列,表示第Ai个Fibonacci数既不是a也不是b也不是c也不是d的倍数.
  每两个数之间用空格隔开.样例输入1 5
2 3 5 7样例输出1 2数据规模和约定  1<=s<=t<=10000,1<=a,b,c,d<=10000

这个数列最大要到一万项,如果用long double定义会有如图这种情况怎么办啊?
zhaohaha 1年前 已收到1个回答 举报

冰雪清凌 幼苗

共回答了22个问题采纳率:100% 举报

用同余的方法:利用一个二维数组f[10001][4],x[4]存放a,b,c,d四个数,
其中f[i ][4]分别表示第i个非波那切数除以x[j]的余数…j=1或2或3或4,
则现在处理f[i][j],其实就是处理余数,再利用非波数的性质,
有递推公式f[i][j]=(f[i-1][j]+f[i-2][j])%x[j],因此f[i][j]的最大值都不会超过a、b、c、d这四个数的最大值…
则f[i][j]=0表示能整除x[j],那么f[i][j]全部不等于0则可..

1年前

2
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 17 q. 0.027 s. - webmaster@yulucn.com