神马作文网求大神关于C++斐波那契数列整除问题
来源：学生作业帮 编辑：神马作文网作业帮 分类：综合作业 时间：2024/11/13 11:45:46
求大神关于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定义会有如图这种情况怎么办啊?
问题描述 已知四个数：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定义会有如图这种情况怎么办啊?
用同余的方法:利用一个二维数组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则可..