A1067. Fibonacci數(shù)列整除問題 時間限制：1.0s ? 內(nèi)存限制：512.0MB ? 總提交次數(shù)：2796 ? AC次數(shù)：496 ? 平均分：51.83 將本題分享到： ? 查看未格式化的試題 ? 提交 ? 試題討論 問題描述 已知四個數(shù)：a，b，c，d，判斷在第s個Fibonacci數(shù)到第t個Fibonacci數(shù)之間哪些數(shù)既不是a也不是b也不是c也不是d的倍數(shù)。 輸入格式 第一行兩個數(shù)，s，t，表示要判斷第s個Fibonacci數(shù)到第t個Fibonacci數(shù)之間（包含第s個和第t個）的Fibonacci數(shù)。
　　第二行四個數(shù)，a，b，c，d，意義如題目描述。 輸出格式 一行若干個數(shù)，A1,A2,A3...An，從小到大排列，表示第Ai個Fibonacci數(shù)既不是a也不是b也不是c也不是d的倍數(shù)。
　　每兩個數(shù)之間用空格隔開。 樣例輸入 1 5
2 3 5 7 樣例輸出 1 2 數(shù)據(jù)規(guī)模和約定 1<=s<=t<=10000, 1<=a,b,c,d<=10000 dp[i][j]表示第i個數(shù)取第j個數(shù)的余數(shù)
轉(zhuǎn)移方程?dp[i][j]=(dp[i-1][j]+dp[i-2][j])%a[j] #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define maxn 10001 #define eps 1e-9 const int inf=0x7fffffff; //無限大 int main() {int f[maxn];f[1]=1;f[2]=1;for(int i=3;i<=10000;i++){f[i]=f[i-1]+f[i-2];}int dp[maxn][4];memset(dp,0,sizeof(0));int s,t,k[4];cin>>s>>t>>k[0]>>k[1]>>k[2]>>k[3];for(int j=0;j<4;j++){dp[1][j]=f[1]%k[j];dp[2][j]=f[2]%k[j];}for(int i=3;i<=10000;i++){for(int j=0;j<4;j++){dp[i][j]=(dp[i-1][j]+dp[i-2][j])%k[j];//cout<<i<<" "<<j<<" "<<dp[i][j]<<endl; }}int first=1;for(int i=s;i<=t;i++){int flag=0;for(int j=0;j<4;j++){if(dp[i][j]!=0)flag++;}if(flag==4){if(first){cout<<i;first=0;}elsecout<<" "<<i;}}cout<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的tsinsen A1067. Fibonacci数列整除问题 dp的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。