求大神关于C++斐波那契数列整除问题
来源:学生作业帮 编辑:百度作业网作业帮 分类:综合作业 时间:2024/08/12 01:23:32
求大神关于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
![](http://img.wesiedu.com/upload/f/4a/f4a7cd7f46c6a80dd130d559d1ca8f66.jpg)
这个数列最大要到一万项,如果用long double定义会有如图这种情况怎么办啊?
问题描述 已知四个数: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
![](http://img.wesiedu.com/upload/f/4a/f4a7cd7f46c6a80dd130d559d1ca8f66.jpg)
这个数列最大要到一万项,如果用long double定义会有如图这种情况怎么办啊?
![求大神关于C++斐波那契数列整除问题](/uploads/image/z/15901233-33-3.jpg?t=%E6%B1%82%E5%A4%A7%E7%A5%9E%E5%85%B3%E4%BA%8EC%2B%2B%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97%E6%95%B4%E9%99%A4%E9%97%AE%E9%A2%98)
用同余的方法:利用一个二维数组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则可..
其中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则可..